Binary Indexed Tree で Range Sum Query
AOJ RSQ
Binary indexed Treeによる解答
BITとは
以下のスライドが参考になります。説明はいろいろなところにあるので、適宜調べてみてください。
- Binary Indexed Tree のはなし
実装
classでライブラリ化しました。自己流ですが、1-indexedの場合をもとに、0-indexedにも対応させました。区間の取り方などいろいろ流儀があると思うのでアレンジしてみてください。
template<typename T> class BIT{ public: int N; vector<T> data; BIT(T _N):N(_N){ data.assign(2 * N + 10, 0); }; // a is 1-indexed void add(int a, T w){ for(int x = a; x <= N; x += x & -x)data[x] += w; } // 1-indexed sum of prefix [0, a] T sum(int a){ T res = 0; for(int x = a; x > 0; x -= x & -x)res += data[x]; return res; } // 1-indexed sum of range [l, r] T sum(int l, int r){return sum(r) - sum(l-1);} // 0-indexed add void add0(int a, T w){add(a + 1, w);} // 0-indexed sum T sum0(int a){return sum(a + 1);} // 0-indexed sum of range T sum0(int l, int r){return sum0(r) - sum0(l-1);} // show the value void debug(){print(data);} };
提出
#include <bits/stdc++.h> using namespace std; #define rep(i,N) for(int i=0;i<int(N);++i) #define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; } typedef long long ll; template<typename T> class BIT{ public: int N; vector<T> data; BIT(T _N):N(_N){ data.assign(2 * N + 10, 0); }; // a is 1-indexed void add(int a, T w){ for(int x = a; x <= N; x += x & -x)data[x] += w; } // 1-indexed sum of prefix [0, a] T sum(int a){ T res = 0; for(int x = a; x > 0; x -= x & -x)res += data[x]; return res; } // 1-indexed sum of range [l, r] T sum(int l, int r){return sum(r) - sum(l-1);} // 0-indexed add void add0(int a, T w){add(a + 1, w);} // 0-indexed sum T sum0(int a){return sum(a + 1);} //0-indexed sum of range T sum0(int l, int r){return sum0(r) - sum0(l-1);} // show the value void debug(){print(data);} }; int n,q; int com, x, y; int main() { cin >> n >> q; BIT<ll> BIT(n); while(q--){ cin >> com >> x >> y; if(com){ cout << BIT.sum(x, y) << endl; } else{ BIT.add(x, y); } } }