Class fenwick_tree_sq

code/data-structures/fenwick_tree.cpp:12–20

  int rsq(int a, int b) { return query(b) - query(a - 1); }
};
struct fenwick_tree_sq {
  int n; fenwick_tree x1, x0;
  fenwick_tree_sq(int _n) : n(_n), x1(fenwick_tree(n)),
    x0(fenwick_tree(n)) { }
  // insert f(y) = my + c if x <= y
  void update(int x, int m, int c) {
    x1.update(x, m); x0.update(x, c); }
  int query(int x) { return x*x1.query(x) + x0.query(x); }
};
void range_update(fenwick_tree_sq &s, int a, int b, int k) {
  s.update(a, k, k * (1 - a)); s.update(b+1, -k, k * b); }
int range_query(fenwick_tree_sq &s, int a, int b) {