Binary Indexed Tree
(datastructure/binaryindexedtree.cpp)

• View this file on GitHub
• Last update: 2021-05-01 12:56:38+09:00

できること

• add(i,a) – $v_i := v_i + a$ とする
• query(l,r) – $\sum_{l \leq i \lt r} v_i$ を求める
• lower_bound(w) – $v_i \geq 0$ の仮定のもと、$\min (\lbrace i \mid \rm{sum}(i) \ge w \rbrace)$ を求める
• upper_bound(w) – $v_i \geq 0$ の仮定のもと、$\min (\lbrace i \mid \rm{sum}(i) \gt w \rbrace)$ を求める

verify 用問題一覧

• lower_bound – AOJ 0343

Required by

• vector/inversion.cpp

Verified with

• test/aoj/0343.test.cpp
• test/aoj/2270.test.cpp
• test/aoj/ALDS1_5_D.test.cpp
• test/aoj/GRL_5_D.test.cpp
• test/yosupo/point_add_range_sum.test.cpp
• test/yosupo/static_range_inversions_query.test.cpp
• test/yosupo/vertex_add_path_sum.test.cpp
• test/yosupo/vertex_add_subtree_sum.test.cpp
• test quantile (test/yukicoder/1732.test.cpp)
• test/yukicoder/2125.test.cpp
• test/yukicoder/4852.test.cpp
• test/yukicoder/5223.test.cpp

Code

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;
#endif

//BEGIN CUT HERE
template<typename T>
class BIT{
private:
  // \sum_{j < i}  v[j]
  T sum(int i){
    T s(0);
    for(int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
public:
  int n;
  vector<T> bit;
  BIT(int n_):n(n_+1),bit(n_+2,0){}

  // v[i] += a
  void add(int i,T a){
    for(int x=++i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }

  // \sum_{l <= i < r} v[i]
  T query(int l,int r){return sum(r)-sum(l);}

  // min({x | sum(x) >= w})
  int lower_bound(const T w){
    if(w<=0) return 0;
    T r=w;
    int x=0,p=1;
    while(p<n) p<<=1;
    for(int k=p;k>0;k>>=1){
      if(x+k<=n and bit[x+k]<r){
        r-=bit[x+k];
        x+=k;
      }
    }
    x++;
    assert(sum(x-1)<w and sum(x)>=w);
    return x;
  }

  // min({x | sum(x) > w})
  int upper_bound(T w){return lower_bound(w+1);}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

#line 1 "datastructure/binaryindexedtree.cpp"

#include <bits/stdc++.h>
using namespace std;
#endif

//BEGIN CUT HERE
template<typename T>
class BIT{
private:
  // \sum_{j < i}  v[j]
  T sum(int i){
    T s(0);
    for(int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
public:
  int n;
  vector<T> bit;
  BIT(int n_):n(n_+1),bit(n_+2,0){}

  // v[i] += a
  void add(int i,T a){
    for(int x=++i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }

  // \sum_{l <= i < r} v[i]
  T query(int l,int r){return sum(r)-sum(l);}

  // min({x | sum(x) >= w})
  int lower_bound(const T w){
    if(w<=0) return 0;
    T r=w;
    int x=0,p=1;
    while(p<n) p<<=1;
    for(int k=p;k>0;k>>=1){
      if(x+k<=n and bit[x+k]<r){
        r-=bit[x+k];
        x+=k;
      }
    }
    x++;
    assert(sum(x-1)<w and sum(x)>=w);
    return x;
  }

  // min({x | sum(x) > w})
  int upper_bound(T w){return lower_bound(w+1);}
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif

Back to top page