差分

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

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:data_structure:binary_indexed_tree [2019/11/17] – [実装] ikatakosprogramming_algorithm:data_structure:binary_indexed_tree [2020/02/26] – [累積和の二分探索] ikatakos
行 141: 行 141:
  
   * [[https://codeforces.com/blog/entry/61364|[Tutorial] Searching Binary Indexed Tree in O(log(N)) using Binary Lifting - Codeforces]]   * [[https://codeforces.com/blog/entry/61364|[Tutorial] Searching Binary Indexed Tree in O(log(N)) using Binary Lifting - Codeforces]]
 +
 +(※以下、sum, add は既述のコードと共通。init内でdepthを定義しておき、lower_boundで探索する)
  
 <sxh python> <sxh python>
 class Bit: class Bit:
-    def __init__(self, n): (+    def __init__(self, n): 
-    def sum(self, i): (略) +        self.size = n 
-    def add(self, i, x): (略)+        self.tree = [0] * (n + 1) 
 +        self.depth = n.bit_length() 
 + 
 +    def sum(self, i): 
 +        s = 0 
 +        while i > 0: 
 +            s += self.tree[i] 
 +            i -= i & -i 
 +        return s 
 + 
 +    def add(self, i, x): 
 +        while i <= self.size: 
 +            self.tree[i] += x 
 +            i += i & -i
  
     def lower_bound(self, x):     def lower_bound(self, x):
-        """ xを越えのindexとその累積和 """ +        """ 累積和がx以上にのindexとの直前までの累積和 """ 
-        sum = 0+        sum_ = 0
         pos = 0         pos = 0
         for i in range(self.depth, -1, -1):         for i in range(self.depth, -1, -1):
             k = pos + (1 << i)             k = pos + (1 << i)
-            if k <= self.size and sum + self.tree[k] < x: +            if k <= self.size and sum_ + self.tree[k] < x: 
-                sum += self.tree[k]+                sum_ += self.tree[k]
                 pos += 1 << i                 pos += 1 << i
-        return pos + 1, sum+        return pos + 1, sum_ 
 </sxh> </sxh>
  
programming_algorithm/data_structure/binary_indexed_tree.txt · 最終更新: 2023/02/08 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0