差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:data_structure:binary_indexed_tree [2020/12/13] – [より柔軟な実装] ikatakos
+++ programming_algorithm:data_structure:binary_indexed_tree [2020/12/13] – [累積和の二分探索] ikatakos
@@ 行 78: / 行 78: @@
 ただし、Python（などインタプリタ言語）では一般的に「''a = add(a, x)''」より「''a += x''」とした方が速い。\\
-柔軟性のために演算を関数で与える関係上、前者の実装となるので、演算が単純でギリギリまで高速化を行いたい場合には向かない。
+柔軟性のために演算を関数で与える関係上、前者の実装となるので、ギリギリまで高速化を行いたい場合には向かない。
@@ 行 90: / 行 90: @@
         self.func = func
         self.idf = identity_factory
-        self.depth = n.bit_length()
     def add(self, i, x):
@@ 行 108: / 行 107: @@
         return s
-    def lower_bound(self, x, lt):
-        """
-        累積和が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, -1, -1):
-            k = pos + (1 << i)
-            new_total = func(total, tree[k])
-            if k <= self.size and lt(new_total, x):
-                total = new_total
-                pos += 1 << i
-        return pos + 1, total
 </sxh>
-listやdictなどのオブジェクトを載せることもできる。\\
+実装について補足。
+Fenwick木では、listやdictなどのオブジェクトを載せることもできる。\\
 その場合の注意点として、Pythonでは、オブジェクトを特に工夫無くコピーするとインスタンス自体が同じとなる。つまりどれか1つへの反映が他の全てに反映されてしまう。
@@ 行 274: / 行 258: @@
 </sxh>
+++++ Injectable版 |
+<sxh python>
+class FenwickTreeInjectable:
+    def __init__(self, n, identity_factory, func):
+        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], x)
+            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, lt):
+        """
+        累積和が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, -1, -1):
+            k = pos + (1 << i)
+            new_total = func(total, tree[k])
+            if k <= self.size and lt(new_total, x):
+                total = new_total
+                pos += 1 << i
+        return pos + 1, total
+</sxh>
+++++