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

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間 = S + a; }}// - S;}int main() { vector<int>a = {1, 2 ...

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

区間の更新がない場合

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

一次元の区間和

累積和を用いることで、

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

で処理がで ...

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

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

2020年2月10日AtCoder二項係数,600点,二次元,区間和

問題へのリンク

問題概要

2次元の平面上で、以下のように関数 f(r,c) を定義する。

f(r,c) := (0,0)から(r,c)までの経路の個数

この時、以下を計算せよ。ただし、\(10^9+7 ...