差分

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

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:data_structure:binary_indexed_tree [2019/11/08] – [累積和のlower bound] ikatakosprogramming_algorithm:data_structure:binary_indexed_tree [2019/11/19] – [累積和の二分探索] ikatakos
行 51: 行 51:
 注意点として、配列のindex等と異なり、添え字は1から始まる。そうしないと効率的に上下の要素を特定できないため。 注意点として、配列のindex等と異なり、添え字は1から始まる。そうしないと効率的に上下の要素を特定できないため。
  
-                8 +  ⇤←←←←←←8 
-        4 +  ⇤←←4 
-    2      6 +  ⇤2    ⇤6    ⇤10 
-  1  3  5  7  9 ...+  1  3  5  7  9   ...
  
  
行 150: 行 150:
     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