BITを2つ使って範囲加算・範囲和 (区間加算・区間和) range add

ライブラリ Binary Indexed Tree

注意

  • range add, range updateは区別しよう
  • 今回はrange add

使った問題

Submisssion

https://atcoder.jp/contests/abc141/submissions/7551683

できること

  • 範囲加算 [a, b) にwを加える
  • 範囲和 [a, b)の和を求める
  • (計算量 : それぞれlog(N))

内部実装

// ei1333's BIT
struct BIT {
  VI data;
  BIT(){}
  BIT(ll sz) {
    resize(sz);
  }
  void resize(ll sz){
    data.assign(++sz, 0);
  }
  ll sum(ll k) {
    ll ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }
  void add(ll k, ll x) {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};
 
// 区間更新・区間和
struct Range{
  BIT P, Q;
  Range(ll sz){
    P.resize(sz+1);
    Q.resize(sz+1);
  }
  // 範囲加算 [a, b) にwを加える
  void update(ll a, ll b, ll w){
    P.add(a, -w*a);
    P.add(b,  w*b);
    Q.add(a,  w);
    Q.add(b, -w);
  }
  // [0, c)
  ll simple_sum(ll c){
    return P.sum(c) + Q.sum(c) * c;
  }
  // [a, b)
  ll sum(ll a, ll b){
    return simple_sum(b) - simple_sum(a);
  }
};

verified

追記：2020/09/19

  • 区間加算はセグ木使う人が多いようだけど、BITのコレで今でも戦えています