Binary Indexed Tree
(data-structure/binary-indexed-tree.hpp)

• View this file on GitHub
• Last update: 2025-10-23 01:57:19+09:00
• Include: #include "data-structure/binary-indexed-tree.hpp"

Fenwick Tree (フェニック木) とも．

列 $A=(A_0,A_1,\dots,A_{N-1})$ があり，はじめ全て $0$．

以下のクエリを，空間計算量 $\Theta(N)$ のもとクエリあたり時間計算量 $O(\log N)$ で処理する．

• add(p, x)：$A_p$ に $x$ を加える．
• sum(p)：和 $A_0+A_1+\cdots+A_{p-1}$ を求める．
• sum(l, r)：和 $A_l+A_1+\cdots+A_{r-1}$ を求める．減算を行う．
• lower_bound(f)：$f(A_0+A_1+\cdots+A_{p-1})$ が真となる最小の $p$ を求める．

一般の区間和で逆元を要求する代わりに segment tree よりも空間・時間計算量の定数倍が軽い．

仕組み

以下 1-indexed で考える．

$0\leq l\leq r\leq N$ に対し以下のように定める．

• $(l,r]\coloneqq{l+1,\cdots,r-1,r}.$
• $A(l,r]\coloneqq A_{l+1}+\cdots+A_{r-1}+A_r.$

また正整数 $i$ を二進表記したときに $2^j$ の位が $1$ であるような最小の $j$ を least-significant set bit と呼び，$\operatorname{lsb}(i)$ で表すことにする．

列 $B=(B_1,B_2,\dots,B_N)$ を $B_i=A(i-2^{\operatorname{lsb}(i)},i]$ を満たすように管理する．

$I_i\coloneqq(i-2^{\operatorname{lsb}(i)},i]$ とする．

$N=8$ のときのイメージ

0     1     2     3     4     5     6     7     8
|                     (0,8]                     |
|         (0,4]         |           -           |
|   (0,2]   |     -     |   (4,6]   |     -     |
|(0,1]|  -  |(2,3]|  -  |(4,5]|  -  |(6,7]|  -  |

add

$p\in I_i$ となるとき $\operatorname{lsb}(p) \leq \operatorname{lsb}(i)$ が必要．

• $\forall j\in I_i$ に対し $\operatorname{lsb}(j) \leq \operatorname{lsb}(i)$ より．

$\operatorname{lsb}(p)=\operatorname{lsb}(i)$ のとき $p\in I_i$ となるのは明らかに $i=p$ のみ．

また $\operatorname{lsb}(p) \lt \operatorname{lsb}(i)$ のとき，$p\in I_i$ となることは $p$ の $2^j$ の位が $0$ であるような $j$ に対して $p$ の $2^j$ の位を $1$，$2^0,\dots,2^{j-1}$ の位を $0$ にして得られる数が $i$ と一致することと同値．

以上をまとめることで，次の要領で計算できることがわかる．

• $p\leq N$ の間以下を繰り返す：
  • $B_p$ に $x$ を加える．
  • $p$ に $2^{\operatorname{lsb}(p)}$ を加える．

sum

$A(0,p]=A(0,p-2^{\operatorname{lsb}(p)}]+B_p$ を用いれば再帰的に計算できる．

lower_bound

長い区間から順に条件を満たすなら付け加えていけばよい．

実装

$2^{\operatorname{lsb}(p)}$ は bit 演算を用いれば p & -p で計算できる．

Verified with

• verify/data-structure/LC_point_add_range_sum.test.cpp

Code

#pragma once

template <class T>
struct BinaryIndexedTree {
  int size;
  vector<T> data;
  BinaryIndexedTree(int n) : size(n), data(n) {}
  void add(int p, T x) {
    for (p++; p <= size; p += p & -p) data[p - 1] += x;
  }
  T sum(int p) {
    T s = 0;
    for (; p; p -= p & -p) s += data[p - 1];
    return s;
  }
  T sum(int l, int r) { return sum(r) - sum(l); }

  template <bool (*f)(T)>
  int lower_bound() const {
    return lower_bound([](T x) { return f(x); });
  }
  template <class F>
  int lower_bound(F f) const {
    if (f(T(0))) return 0;
    int x = 0, r = 1;
    while (r < size) r = r << 1;
    T s = 0;
    for (int len = r; len > 0; len >>= 1) {
      if (x + len < size && !f(s + data[x + len]))
        s += data[x += len];
    }
    return x + 1;
  }
};

/**
 * @brief Binary Indexed Tree
 * @docs docs/data-structure/binary-indexed-tree.md
 */

#line 2 "data-structure/binary-indexed-tree.hpp"

template <class T>
struct BinaryIndexedTree {
  int size;
  vector<T> data;
  BinaryIndexedTree(int n) : size(n), data(n) {}
  void add(int p, T x) {
    for (p++; p <= size; p += p & -p) data[p - 1] += x;
  }
  T sum(int p) {
    T s = 0;
    for (; p; p -= p & -p) s += data[p - 1];
    return s;
  }
  T sum(int l, int r) { return sum(r) - sum(l); }

  template <bool (*f)(T)>
  int lower_bound() const {
    return lower_bound([](T x) { return f(x); });
  }
  template <class F>
  int lower_bound(F f) const {
    if (f(T(0))) return 0;
    int x = 0, r = 1;
    while (r < size) r = r << 1;
    T s = 0;
    for (int len = r; len > 0; len >>= 1) {
      if (x + len < size && !f(s + data[x + len]))
        s += data[x += len];
    }
    return x + 1;
  }
};

/**
 * @brief Binary Indexed Tree
 * @docs docs/data-structure/binary-indexed-tree.md
 */

Back to top page