差分

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

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

両方とも前のリビジョン 前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:data_structure:binary_indexed_tree [2019/11/07]
ikatakos
programming_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   ​...
  
  
ライン 136: ライン 136:
   * [[https://​freestylewiki.xyz/​fswiki/​wiki.cgi?​page=%E3%83%95%E3%82%A7%E3%83%8B%E3%83%83%E3%82%AF%E6%9C%A8%28Binary+Indexed+Tree%29#​p12|フェニック木(Binary Indexed Tree) - FreeStyleWiki]]   * [[https://​freestylewiki.xyz/​fswiki/​wiki.cgi?​page=%E3%83%95%E3%82%A7%E3%83%8B%E3%83%83%E3%82%AF%E6%9C%A8%28Binary+Indexed+Tree%29#​p12|フェニック木(Binary Indexed Tree) - FreeStyleWiki]]
  
-====累積和のlower bound====+=====累積和の二分探索=====
  
-累積和が $x$ のindexや、$x$ を越えない最大のindexとその時の累積和を得ることができる。+二分探索により、累積和が $x$ のindexや、$x$ を越えない最大のindexとその時の累積和などを得ることができる。
  
   * [[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]]
ライン 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 · 最終更新: 2019/11/19 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0