Binary-Indexed Tree
Jump to navigation
Jump to search
template <typename T>
class BIT {
private:
T a[N + 10];
public:
void add(int x, T d) {
x++;
while (x < N) {
a[x] += d;
x += x & -x;
}
}
T query(int x) {
x++; T ret = 0;
while (x) {
ret += a[x];
x -= x & -x;
}
return ret;
}
T query_interval(int a, int b) {
// closed interval
return query(b) - query(a - 1);
}
/***** The following should be used exclusively *****/
inline T query2(int x) {
// used to query some value (not some sum)
return query(x);
}
void add2(int a, int b, T d) {
add(a, d); add(b + 1, -d);
}
};