[AOJ] DSL_2_B Range Sum Query (RSQ)

Range Sum Query (RSQ)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

配列の値を変えるクエリとその配列の区間和を答えるクエリに対応する問題です。セグメント木や平方分割などで対処できますが、BITというデータ構造を使って解答できるようです。

Binary Indexed Tree

解説は下のサイト。

http://anctgcc.hatenablog.com/entry/2014/12/03/194140

イメージとしては累積和を分割した区間で持っておくような感じでしょうか。

ソースコード

感想

平方分割が多段階になった感じですか?

他の問題でも使えるように覚えておきたいですね。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする