BIT (Fenwick Tree)
(src/data-structure/BIT.hpp)

• View this file on GitHub
• Last update: 2024-02-23 08:47:21+09:00
• Include: #include "src/data-structure/BIT.hpp"

• 参考実装：AC Library

使い方

1 点加算・区間和ができるデータ構造

• BIT(ll n)：長さ $n$ の配列を作る
• void add(ll i, ll x)：A[i] += x を行う
• ll sum(ll r)：sum(A[:r]) を求める
• ll sum(ll l, ll r)：sum(A[l:r]) を求める

計算量 $O(\log n)$ / クエリ

Verified with

• test/data-structure/BIT.test.cpp

Code

struct BIT {
   vector<ll> a;
   BIT(ll n) : a(n + 1) {}
   void add(ll i, ll x) {  // A[i] += x
      i++;
      while(i < sz(a)) {
         a[i] += x;
         i += i & -i;
      }
   }
   ll sum(ll r) {
      ll s = 0;
      while(r) {
         s += a[r];
         r -= r & -r;
      }
      return s;
   }
   ll sum(ll l, ll r) {  // sum of A[l, r)
      return sum(r) - sum(l);
   }
};

#line 1 "src/data-structure/BIT.hpp"
struct BIT {
   vector<ll> a;
   BIT(ll n) : a(n + 1) {}
   void add(ll i, ll x) {  // A[i] += x
      i++;
      while(i < sz(a)) {
         a[i] += x;
         i += i & -i;
      }
   }
   ll sum(ll r) {
      ll s = 0;
      while(r) {
         s += a[r];
         r -= r & -r;
      }
      return s;
   }
   ll sum(ll l, ll r) {  // sum of A[l, r)
      return sum(r) - sum(l);
   }
};

Back to top page