2020年3月20日その他区間和, 区間, 累積和, 配列

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間

累積和の気持ち累積和とは

累積和は、「始めから i 番目までの和を前処理で計算したもの」です

2020年3月15日AtCoder競プロ, セグメント木, 区間, 更新, データ構造, set, imos法, 遅延評価セグメント木, イベントソート, 座標圧縮

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
\(i\) 番目の道路工事は時刻 \(S_i−0.5\) から時刻 \(T_i−0.5\) まで座標 \(X_i\) ...

2020年3月10日動的計画法DP, テーマ記事, 競プロ, 区間, 区間DP, 区間の除去・圧縮・合体

競技プログラミングで良く使われる動的計画法の1種、「区間DP」と呼ばれるものについてまとめました。

区間DPとは

区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。

基本的には、以下のような DP ...

2020年3月8日AtCoder剰余, 数え上げ, 500点, 競プロ, 区間, 素数, Pで割り切れる

問題概要

長さ N の数 S が与えられる。
素数 P で割り切れるような区間の選び方は何通りあるか?

制約\(1 \leq N \leq 2 \times 10^5\)
\(2 \leq P \leq 10000\ ...

2020年3月6日その他区間和, テーマ記事, 競プロ, 区間, 累積和, imos法, 二次元区間和

区間の更新がない場合

区間の更新が生じない場合は、累積和を用いることで高速にクエリを処理できます。

一次元の区間和

累積和を用いることで、

前処理:\(O(N)\)
クエリ:\(O(1)\)

で処理がで ...

2020年3月5日データ構造BIT, 区間和, 競プロ, 二分探索, セグメント木, 区間, データ構造, RAQ, RSQ, 転倒数, 二次元BIT

Binary Indexed Tree (またはフェニック木) は 数列 \(a_1, a_2, a_3, \cdots, a_n\) が与えられた時に、以下のようなことがそれぞれ \(O(log n)\) で実現できるデータ構造のこ ...

2020年3月2日AtCoder500点, セグメント木, 区間, set, クエリ

問題概要

長さ N の英小文字からなる文字列 S を与えられ、以下の二種類のクエリ合計 Q 個を処理する。

S の \(i_q\) 番目を \(c_q\) に変更する
S の \(i_q\) 番目から \(r_q\) 番目ま ...

2020年2月27日データ構造二分探索, セグメント木, 二分木, 完全二分木, 区間, モノイド, 更新, RMQ, RUQ, データ構造, RAQ, RSQ

セグメント木とは

セグメント木とは、完全二分木(全ての葉の深さが等しい木)によって実装された、区間を扱うのに適したデータ構造のことです。

区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミング ...