差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:binary_indexed_tree [2020/06/04] – ikatakos | programming_algorithm:data_structure:binary_indexed_tree [2020/12/13] – [実装] ikatakos | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======Binary Indexed Tree====== | + | ======Binary Indexed Tree（Fenwick Tree）====== |
| =====概要===== | =====概要===== | ||
| 行 9: | 行 9: | ||
| * 数列 $a_1, | * 数列 $a_1, | ||
| * 以下の2つの要求を処理する | * 以下の2つの要求を処理する | ||
| - | * $a_i$ に $x$ を加算（$1 \le i \le n$） | + | * $a_i$ に $x$ を加算（$1 \le i \le N$） |
| - | * $a_s$ から $a_t$ までの合計を得る（$1 \le s \le t \le n$） | + | * $a_s～a_t$ の合計を得る（$1 \le s \le t \le N$） |
| Binary Indexed Treeは、この2つを高速に行える。 | Binary Indexed Treeは、この2つを高速に行える。 | ||
| 行 70: | 行 70: | ||
| 0001 0011 0101 【0111】 | 0001 0011 0101 【0111】 | ||
| + | |||
| + | ==== より柔軟な実装 ==== | ||
| + | |||
| + | Fenwick木に載せられるのは足し算だけでなく、XORやかけ算、また（わりと致命的な制約はあるが一応は）minやmaxも載せられる。 | ||
| + | |||
| + | 「初期値」と「演算する関数」さえ決めればよいので、これを外部注入できるようにすると、柔軟な実装になる。 | ||
| + | |||
| + | ただし、Python（などインタプリタ言語）では一般的に「'' | ||
| + | 柔軟性のために演算を関数で与える関係上、前者の実装となるので、演算が単純でギリギリまで高速化を行いたい場合には向かない。 | ||
| + | |||
| + | |||
| + | ++++ Python3 | | ||
| + | |||
| + | <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 | ||
| + | |||
| + | 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 | ||
| + | </ | ||
| + | |||
| + | listやdictなどのオブジェクトを載せることもできる。\\ | ||
| + | Pythonでは、オブジェクトを特に工夫無くコピーするとインスタンス自体が同じとなる。つまりどれか1つへの反映が他の全てに反映されてしまう。 | ||
| + | |||
| + | それを防ぐため、'' | ||
| + | |||
| + | <sxh python> | ||
| + | # だめな例 | ||
| + | a = [0, 0] | ||
| + | aaa = [a] * 3 | ||
| + | print(aaa) | ||
| + | |||
| + | aaa[0][0] = 5 | ||
| + | print(aaa) | ||
| + | |||
| + | |||
| + | # 以下の実装だと、上のようなことが発生する | ||
| + | class FenwickTreeInjectable: | ||
| + | def __init__(self, | ||
| + | self.size = n | ||
| + | self.tree = [identity_element] * (n + 1) # ←ここがまずい | ||
| + | self.func = func | ||
| + | | ||
| + | ...略 | ||
| + | |||
| + | </ | ||
| + | |||
| + | ++++ | ||
