FenwickTree
(lib/data_structure/fenwick_tree.py)

• View this file on GitHub
• Last update: 2022-07-28 01:03:27+09:00

Fenwick Tree (Binary Indexed Tree)

$T$ 型の要素数 $n$ の配列に対して、値の一点加算と区間和の取得をともに $O(\log{N})$ で行えるデータ構造。

区間和が効率的に計算できる累積和では値の更新に $O(N)$ かかるところ、 Fenwick Tree では値の更新とそれによる変化を効率的に反映することができる。

Segment Tree と比較して実装がシンプルで定数倍が軽いが、区間和を計算するためには $T$ に逆元が存在する必要がある。

また、imos 法的に使えば 区間加算、一点取得 としても使うことができる。

Implementations

def __init__(self, n: int)

サイズ n の FenwickTree を生成する
初期値はすべて $0$
（デフォルトでは $T$ = int として扱われる）
$O(N)$

---

def build(self, a: Sequence[T])

a で初期化する
はみ出た分は無視される
$O(N\log{N})$

---

def add(self, i: int, x: T)

i 番目の要素に x を加算する
i が FenwickTree のサイズより大きい場合は無視される
$O(\log{N})$

---

def set(self, i: int, x: T)

i 番目の要素を x に更新する
i が FenwickTree のサイズより大きい場合は IndexError を送出する
$O(\log{N})$

---

def sum(self, l: int, r: int) -> int

区間 [l, r] の和を返す
l または r が FenwickTree のサイズより大きい場合は IndexError を送出する
$O(\log{N})$

---

def at(self, i: int) -> T

i 番目の要素の値を返す
i が FenwickTree のサイズより大きい場合は IndexError を送出する
$O(\log{N})$

---

Verified with

• verify/data_structure/point_add_range_sum.test.py
• verify/data_structure/static_range_sum__fenwick_tree.test.py

Code

T = int


class FenwickTree:
    def __init__(self, n: int):
        self._n = n
        self._a = [0] * (n + 1)

    def build(self, a):
        for i, ai in enumerate(a):
            self.add(i, ai)

    def add(self, i: int, x: T):
        i += 1
        while i <= self._n:
            self._a[i] += x
            i += i & -i

    def set(self, i: int, x: T):
        self.add(i, x - self._sum(i) + self._sum(i - 1))

    def sum(self, l: int, r: int) -> T:
        return self._sum(r) - self._sum(l - 1)

    def _sum(self, i: int) -> T:
        i += 1
        s = 0
        while i > 0:
            s += self._a[i]
            i -= i & -i
        return s

    def at(self, i: int) -> T:
        return self._sum(i) - self._sum(i - 1)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.6/x64/lib/python3.10/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
  File "/opt/hostedtoolcache/Python/3.10.6/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page