| 1 | struct fenwick_tree { |
| 2 | int n; vi data; |
| 3 | fenwick_tree(int _n) : n(_n), data(vi(n)) { } |
| 4 | void update(int at, int by) { |
| 5 | while (at < n) data[at] += by, at |= at + 1; } |
| 6 | int query(int at) { |
| 7 | int res = 0; |
| 8 | while (at >= 0) res += data[at], at = (at & (at + 1)) - 1; |
| 9 | return res; } |
| 10 | int rsq(int a, int b) { return query(b) - query(a - 1); } |
| 11 | }; |
| 12 | struct fenwick_tree_sq { |
| 13 | int n; fenwick_tree x1, x0; |
| 14 | fenwick_tree_sq(int _n) : n(_n), x1(fenwick_tree(n)), |