差分
このページの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)====== |
=====概要===== | =====概要===== | ||
行 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 | ||
+ | | ||
+ | ...略 | ||
+ | |||
+ | </ | ||
+ | |||
+ | ++++ | ||