差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:data_structure:binary_indexed_tree [2019/11/08]
ikatakos [累積和のlower bound]
programming_algorithm:data_structure:binary_indexed_tree [2020/02/26] (現在)
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   ​...
  
  
ライン 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.1573173397.txt.gz · 最終更新: 2019/11/08 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0