BIT-range.cpp

// BIT with range updates, inspired by Petr Mitrichev
struct BIT {
  int n;
  vector<int> slope;
  vector<int> intercept;
  // BIT can be thought of as having entries f[1], ..., f[n]
  // which are 0-initialized
  BIT(int n) : n(n), slope(n + 1), intercept(n + 1) {}
  // returns f[1] + ... + f[idx-1]
  // precondition idx <= n+1
  int query(int idx) {
    int m = 0, b = 0;
    for (int i = idx - 1; i > 0; i -= i & -i) {
      m += slope[i];
      b += intercept[i];
    }
    return m * idx + b;
  }
  // adds amt to f[i] for i in [idx1, idx2)
  // precondition 1 <= idx1 <= idx2 <= n+1 (you can't update
  // element 0)
  void update(int idx1, int idx2, int amt) {
    for (int i = idx1; i <= n; i += i & -i) {
      slope[i] += amt;
      intercept[i] -= idx1 * amt;
    }
    for (int i = idx2; i <= n; i += i & -i) {
      slope[i] -= amt;
      intercept[i] += idx2 * amt;
    }
  }
};