Binary Indexed Tree(単独加算,区間総和)

keyword:

カートに追加

overview

次のクエリを処理できる. - 1つの要素を加算・減算する. - 区間の要素の総和を計算する. 1-indexedの実装に注意. 何度も加減算を繰り返すと内部でオーバーフローを起こす可能性.

usage

Bitree(int n)
; [1..n] の配列を確保する.
T Bitree::sum(int r)
; [1..r]の範囲の値の和を求める.
T Bitree::add(int idx, T val)
; idx の要素の値をval増やす
; 1-indexed.

verified

二分探索が未だ出来ていない

references

プログラミングコンテストチャレンジブック

code