区間加算が行えるBIT

遅延セグ木よりも定数倍速い。

• 遅延セグ木のコードの実行時間 : 1154ms
• 遅延セグ木部分だけをBITに置き換えたコードの実行時間 : 701ms

参考にしたページ
Binary Indexed Tree のはなし - hos.ac

verify済み
Submission #70922924 - Codeforces

struct FenwickTree {
  vector<long long> v;
  int n;
  FenwickTree(int n) : n(n), v(n) {}
  void add(int i, long long x) {
    i++;
    while (i <= n) {
      v[i - 1] += x;
      i += i & -i;
    }
  }
  long long get(int i) {
    long long r = 0;
    while (i >= 1) {
      r += v[i - 1];
      i -= i & -i;
    }
    return r;
  }
};
 
struct ExFenwickTree {
  FenwickTree p, q;
  ExFenwickTree(int n) : p(n + 1), q(n + 1) {}
  void add(int l, int r, long long w) {
    p.add(l, -w * l);
    p.add(r, w * r);
    q.add(l, w);
    q.add(r, -w);
  }
  long long get(int r) {
    return p.get(r) + q.get(r) * r;
  }
};