差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:binary_indexed_tree [2020/12/13] – [実装] ikatakos | programming_algorithm:data_structure:binary_indexed_tree [2023/02/08] – ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
======Binary Indexed Tree(Fenwick Tree)====== | ======Binary Indexed Tree(Fenwick Tree)====== | ||
+ | |||
+ | 区間の和に対するクエリ(Range Sum Query)を効率的に処理するデータ構造。((和以外にも使える。後述)) | ||
+ | |||
+ | Binary Indexed Tree、BIT、発案者の名前からFenwick Treeともいう。 | ||
=====概要===== | =====概要===== | ||
[[http:// | [[http:// | ||
- | |||
- | Range Sum Query(区間の和)に対する効率的なデータ構造。 | ||
* 数列 $a_1, | * 数列 $a_1, | ||
- | * 以下の2つの要求を処理する | + | * 以下の2つのクエリを処理する |
- | * $a_i$ に $x$ を加算($1 \le i \le N$) | + | * 「'' |
- | * $a_s~a_t$ の合計を得る($1 \le s \le t \le N$) | + | * 「'' |
Binary Indexed Treeは、この2つを高速に行える。 | Binary Indexed Treeは、この2つを高速に行える。 | ||
- | これだけ見ると「そんなのが何の役に立つの?」って感じだが、頭のいい人だと全然関係ないように見える問題を変換して効率的に解いたりしちゃうらしい。 | + | 合計が $a_1$ からしか得られない制約があるが、$sum(a_s~a_t) = sum(a_1~a_t) - sum(a_1~a_{s-1})$ |
=====実装===== | =====実装===== | ||
行 49: | 行 51: | ||
</ | </ | ||
- | 注意点として、配列のindex等と異なり、添え字は1から始まる。その方が効率的に上下の要素を特定できるため。 | + | BITは、1つの配列として保持できる。 |
+ | |||
+ | ただし、一般的な配列のindexと異なり、添え字は1から始まる。その方が効率的に上下の要素を特定できるため。\\ | ||
+ | (実装上は、0 の部分は使わないで1つ長めに作っておくのがよい) | ||
⇤←←←←←←8 | ⇤←←←←←←8 | ||
行 55: | 行 60: | ||
⇤2 | ⇤2 | ||
1 3 5 7 9 ... | 1 3 5 7 9 ... | ||
+ | | ||
+ | index | ||
+ | 1 a1 | ||
+ | 2 a1+a2 | ||
+ | 3 a3 | ||
+ | 4 a1+a2+a3+a4 | ||
+ | 5 a5 | ||
+ | 6 a5+a6 | ||
+ | 7 a7 | ||
+ | 8 a1+a2+a3+a4+a5+a6+a7+a8 | ||
+ | : : | ||
添え字を2進数にしたもの。 | 添え字を2進数にしたもの。 | ||
行 63: | 行 79: | ||
0001 0011 0101 0111 1001 ... | 0001 0011 0101 0111 1001 ... | ||
- | 「$a_1 ~ a_7$ の和」を求めるときに足される箇所。7を表す | + | ここから「$a_1 ~ a_7$ の和」を求めるときに参照される箇所。\\ |
+ | $7$ を表す | ||
- | | + | |
- | ⇤─←─←【0100】 | + | |
- | ⇤─0010 | + | ⇤─0010 |
- | 0001 0011 0101 【0111】 | + | 0001 0011 0101 【0111】 |
+ | |||
+ | 「$a_5$ に $x$ を足す」処理をするときに参照される箇所。\\ | ||
+ | $5$ を表す '' | ||
+ | 辿り方としては、'' | ||
+ | |||
+ | 【⇤─←─←─←─←─←─←─1000】 | ||
+ | ⇤─←─←─0100 | ||
+ | ⇤─0010 | ||
+ | 0001 0011 【0101】 | ||
+ | |||
+ | 0101 + 一番下の1: | ||
+ | 0110 + 一番下の1: | ||
行 78: | 行 107: | ||
ただし、Python(などインタプリタ言語)では一般的に「'' | ただし、Python(などインタプリタ言語)では一般的に「'' | ||
- | 柔軟性のために演算を関数で与える関係上、前者の実装となるので、演算が単純でギリギリまで高速化を行いたい場合には向かない。 | + | 柔軟性のために演算を関数で与える関係上、前者の実装となるので、ギリギリまで高速化を行いたい場合には向かない。 |
行 106: | 行 135: | ||
i -= i & -i | i -= i & -i | ||
return s | return s | ||
+ | |||
</ | </ | ||
- | listやdictなどのオブジェクトを載せることもできる。\\ | + | 実装について補足。 |
- | Pythonでは、オブジェクトを特に工夫無くコピーするとインスタンス自体が同じとなる。つまりどれか1つへの反映が他の全てに反映されてしまう。 | + | |
- | それを防ぐため、'' | + | Fenwick木では、listやdictなどのオブジェクトを載せることもできる。\\ |
+ | その場合の注意点として、Pythonでは、オブジェクトを特に工夫無くコピーするとインスタンス自体が同じとなる。 | ||
+ | つまりどれか1つへの反映が他の全てに反映されてしまう。 | ||
+ | |||
+ | それを防ぐため、'' | ||
+ | これなら毎回別のものが生成される。 | ||
+ | |||
+ | <sxh python; | ||
- | <sxh python> | ||
- | # だめな例 | ||
a = [0, 0] | a = [0, 0] | ||
aaa = [a] * 3 | aaa = [a] * 3 | ||
行 148: | 行 182: | ||
* $a_i$ の値を得る($1 \le i \le n$) | * $a_i$ の値を得る($1 \le i \le n$) | ||
- | この場合は、差分に着目することで、BITをそのまま利用できる。(上記pdf参照) | + | この場合は、差分に着目することで、BITをそのまま利用できる。 |
* $a_s~a_t$ に一律 $x$ を加算→「$s$ に $x$、$t+1$ に $-x$ を加算」 | * $a_s~a_t$ に一律 $x$ を加算→「$s$ に $x$、$t+1$ に $-x$ を加算」 | ||
* $a_i$ の値を取得→「$1~i$ の合計を取得」 | * $a_i$ の値を取得→「$1~i$ の合計を取得」 | ||
+ | |||
+ | * [[http:// | ||
なお、見ての通り添え字が $n+1$ まで参照される可能性があるので、便宜上、BITのサイズは1大きい値で作っておく | なお、見ての通り添え字が $n+1$ まで参照される可能性があるので、便宜上、BITのサイズは1大きい値で作っておく | ||
行 161: | 行 197: | ||
< | < | ||
+ | |||
+ | だが、これに関しては遅延評価セグメント木などを使った方が、汎用性が高いかもしれない。 | ||
<sxh python> | <sxh python> | ||
行 184: | 行 222: | ||
=====区間の最大値・最小値===== | =====区間の最大値・最小値===== | ||
- | Segment Treeほどの柔軟性は無いが、いくらかの制約された条件下で、区間最大値・最小値の管理にも使える(以下は最大値の例) | + | Segment Treeほどの柔軟性は無いが、いくらかの制約下で、区間最大値・最小値の管理にも使える(以下は最大値の例) |
- | * $update(i, x)$: $a_i$ を $x$ で更新する。この際、$x$ は必ず元の | + | * $update(i, x)$: $a_i$ を $x$ で更新する。 |
- | * $getmax(i)$: | + | * この更新とは「上書き」でなくて「作用」でなくてはならない。 |
+ | * つまり、$a_i←x$ は不可で、$a_i←\max(a_i, | ||
+ | * $getmax(i)$: | ||
+ | * 必ず1からの最大値であり、途中からの区間 | ||
単純に、上記のコードの加算を、MAXを取る操作に置きかえればよい。 | 単純に、上記のコードの加算を、MAXを取る操作に置きかえればよい。 | ||
行 211: | 行 252: | ||
</ | </ | ||
- | 少し理解は難しくなるが、BITを2本使って管理することで、上記の制約を無くした区間最大値・最小値も得られる。 | + | 少し理解は難しくなるが、BITを2本使って管理することで、制約をなくした区間最大値・最小値を取得する実装もできる。 |
* [[https:// | * [[https:// | ||
* [[https:// | * [[https:// | ||
+ | |||
+ | ただし使い方がややトリッキーだし、このために実装すべき処理も多いため、 | ||
+ | より柔軟性高く区間取得が可能なSegment Treeを使った方が簡単かもしれない。 | ||
+ | |||
+ | ++++ 少し詳細 | | ||
+ | |||
+ | BITの配列 $data[i]$ は、$(i-LSB(i), | ||
+ | $LSB(i)$ は、$i$ の最下位ビットを指す。 | ||
+ | | ||
+ | BIT1 | ||
+ | ⇤─←─←─←─←─←─←─1000 | ||
+ | ⇤─←─←─0100 | ||
+ | ⇤─0010 | ||
+ | 0001 0011 0101 0111 1001 1011 1101 1111 | ||
+ | | ||
+ | i=1100 のLSBは 0100 → 1100 - 0100 = 1000 → 1001~1100 の情報を持っている | ||
+ | |||
+ | これと同様にもう1つ、$[i, | ||
+ | |||
+ | BIT2 | ||
+ | 1000─⇥─⇥─⇥─⇥─⇥─⇥─⇥ | ||
+ | 0100─⇥─⇥─⇥ | ||
+ | 0010─⇥ | ||
+ | 0001 0011 0101 0111 1001 1011 1101 1111 | ||
+ | |||
+ | $[5,13]$ の範囲(2進数では[0101, | ||
+ | |||
+ | * ①5から、13を超える直前まで、BIT1上の親を辿る($i$ に $LSB(i)$ を足していく) | ||
+ | * → 5, 6, 8 | ||
+ | * ②13から、5未満になる直前まで、BIT2上の親を辿る($i$ の $LSB(i)$ を0にしていく) | ||
+ | * → 13, 12, 8 | ||
+ | * ③このとき、必ず同じindex(8)で終了する | ||
+ | * ④終了したindexを除き、①で辿ったindexを、BIT2上で参照する(BIT2[5], | ||
+ | * ⑤終了したindexを除き、②で辿ったindexを、BIT1上で参照する(BIT1[12], | ||
+ | * ⑥ ④, | ||
+ | |||
+ | 上書き更新も一応できるらしいが、 | ||
+ | たとえば [1,4] のどこかが更新され、それを元に [1,8] を更新するときは、[5, | ||
+ | セグメント木なら兄弟ノードを参照すればすぐ取得できるのだが、BITでの実装の場合は毎回取得が必要になり、$O(\log^2{N})$ かかる? | ||
+ | (なんか上手いこと $O(\log{N})$ でやる方法が論文で説明されているっぽいが、よくわからない) | ||
+ | |||
+ | |||
+ | ++++ | ||
=====累積和の二分探索===== | =====累積和の二分探索===== | ||
行 255: | 行 339: | ||
</ | </ | ||
+ | |||
+ | ++++ Injectable版 | | ||
+ | |||
+ | <sxh python> | ||
+ | class FenwickTreeInjectable: | ||
+ | def __init__(self, | ||
+ | self.size = n | ||
+ | self.tree = [identity_factory() for _ in range(n + 1)] | ||
+ | self.func = func | ||
+ | self.idf = identity_factory | ||
+ | self.depth = n.bit_length() | ||
+ | |||
+ | def add(self, i, x): | ||
+ | tree = self.tree | ||
+ | func = self.func | ||
+ | while i <= self.size: | ||
+ | tree[i] = func(tree[i], | ||
+ | i += i & -i | ||
+ | |||
+ | def sum(self, i): | ||
+ | s = self.idf() | ||
+ | tree = self.tree | ||
+ | func = self.func | ||
+ | while i > 0: | ||
+ | s = func(s, tree[i]) | ||
+ | i -= i & -i | ||
+ | return s | ||
+ | |||
+ | def lower_bound(self, | ||
+ | """ | ||
+ | 累積和がx以上になる最小のindexと、その直前までの累積和(未検証) | ||
+ | |||
+ | :param lt: lt(a, b) で a < b ならTrueを返す関数 | ||
+ | """ | ||
+ | total = self.idf() | ||
+ | pos = 0 | ||
+ | tree = self.tree | ||
+ | func = self.func | ||
+ | for i in range(self.depth, | ||
+ | k = pos + (1 << i) | ||
+ | new_total = func(total, tree[k]) | ||
+ | if k <= self.size and lt(new_total, | ||
+ | total = new_total | ||
+ | pos += 1 << i | ||
+ | return pos + 1, total | ||
+ | </ | ||
+ | |||
+ | ++++ | ||
+ | |||
+ | ===== 添え字の範囲が大きい場合 ===== | ||
+ | |||
+ | BITは通常の配列で管理できると言ったが、取り得る添え字の上限が $N=10^{18}$ とかだと | ||
+ | そもそもそれだけの配列をメモリ上に確保できない。 | ||
+ | |||
+ | だが、 | ||
+ | |||
+ | * はじめ、全ての $a_i=0$ である | ||
+ | * 実際に飛んでくるクエリの個数は $Q=10^5$ 回など高が知れている | ||
+ | |||
+ | という場合は工夫次第で処理できる。 | ||
+ | |||
+ | ==== 座標圧縮 ==== | ||
+ | |||
+ | 飛んでくるクエリを全て先読みできる場合に使える。 | ||
+ | |||
+ | * [[https:// | ||
+ | |||
+ | BITでは添え字の大小関係だけが意味を持つので、 | ||
+ | クエリを先読みして、加算または取得クエリで登場する添え字を大小関係を保ったまま $1~Q$ に振り直してやればよい。 | ||
+ | |||
+ | これで計算量は $Q$ クエリ通して $O(Q\log{Q})$ で済む。 | ||
+ | |||
+ | ==== 動的木 ==== | ||
+ | |||
+ | データを配列でなく辞書型で持ち、必要な(0でない)部分だけ値を記録するようにする。 | ||
+ | |||
+ | ⇤←←←←←←8 | ||
+ | ⇤←←4 | ||
+ | ⇤2 | ||
+ | 1 3 5 7 9 ... | ||
+ | | ||
+ | データを持つ辞書を data とする。 | ||
+ | 初期状態から 5 に x 加算する場合、data[5], | ||
+ | 逆に言うと他は 0 のままなので、明示的にデータを持たなくていい。 | ||
+ | |||
+ | クエリが先読みできない場合にも使える。 | ||
+ | |||
+ | 計算量は $O(Q \log{N})$ だし、辞書で添え字から値を参照するコストも一般的に配列より重いので、若干、座標圧縮より計算は重くなる。 | ||
+ | |||
+ | |||
+ | ===== 2次元木 ===== | ||
+ | |||
+ | 以下のクエリを処理できる。 | ||
+ | |||
+ | * $H \times W$ の2次元グリッドがあり、各マスに整数が記録される | ||
+ | * 「'' | ||
+ | * 「'' | ||
+ | |||
+ | 実装としては、BITの各ノードに整数でなく、2次元目のBITを持たせる感じ。 | ||
+ | |||
+ | ⇤←←←←←←8 | ||
+ | ⇤←←4 | ||
+ | ⇤2 | ||
+ | 1 3 5 7 9 ... | ||
+ | | ||
+ | (5, 3) に add クエリが来た場合、 | ||
+ | まず1次元目の 5 に関して、data[5], | ||
+ | | ||
+ | このそれぞれのノードが持つ BIT について、 | ||
+ | 2次元目の 3 に関しては 3, 4, 8 を参照すれば良いので、 | ||
+ | | ||
+ | data[5][3], data[5][4], data[5][8], | ||
+ | data[6][3], data[6][4], data[6][8], | ||
+ | data[8][3], data[8][4], data[8][8], | ||
+ | | ||
+ | 以上のノードに加算してやればよい。 | ||
+ | |||
+ | データの持たせ方は動的木で実装した方がよい。 | ||
+ | |||
+ | 配列で持つ方針だと $O(HW)$ の記録容量が必要になる。\\ | ||
+ | クエリが少なくて座標圧縮しても、$O(Q^2)$ 以下にはならない。\\ | ||
+ | もちろん、それで間に合うような制約であれば配列で実装してもよい。 | ||
+ | |||
+ | $HW$ も $Q^2$ も大きすぎる場合は、動的木で実装すればメモリを抑えられる。\\ | ||
+ | 必要空間量は $O(Q (\log{Q})^2)$ となり、$Q=10^5$ 弱くらいなら問題なくなる。 | ||
+ | |||
+ | ++++ Python による Injectable版の実装 | | ||
+ | |||
+ | <sxh python> | ||
+ | from collections import defaultdict | ||
+ | from typing import TypeVar, Callable, Generic | ||
+ | |||
+ | T = TypeVar(' | ||
+ | |||
+ | |||
+ | class Dynamic2dFenwickTree(Generic[T]): | ||
+ | """ | ||
+ | (T, func): 可換モノイド | ||
+ | factory: 単位元の生成関数 | ||
+ | """ | ||
+ | |||
+ | def __init__(self, | ||
+ | self.data = defaultdict(lambda: | ||
+ | self.h = h | ||
+ | self.w = w | ||
+ | self.func = func | ||
+ | self.factory = factory | ||
+ | |||
+ | def add_point(self, | ||
+ | """ | ||
+ | data = self.data | ||
+ | func = self.func | ||
+ | i += 1 | ||
+ | j += 1 | ||
+ | while i <= self.h: | ||
+ | node = data[i] | ||
+ | k = j | ||
+ | while k <= self.w: | ||
+ | node[k] = func(node[k], | ||
+ | k += k & -k | ||
+ | i += i & -i | ||
+ | |||
+ | def get_range(self, | ||
+ | data = self.data | ||
+ | func = self.func | ||
+ | result = self.factory() | ||
+ | i = min(i + 1, self.h) | ||
+ | j = min(j + 1, self.w) | ||
+ | while i > 0: | ||
+ | if i in data: | ||
+ | node = data[i] | ||
+ | k = j | ||
+ | while k > 0: | ||
+ | if k in node: | ||
+ | result = func(result, | ||
+ | k -= k & -k | ||
+ | i -= i & -i | ||
+ | return result | ||
+ | </ | ||
+ | |||
+ | ++++ | ||