差分

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

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:data_structure:binary_indexed_tree [2019/11/07] ikatakosprogramming_algorithm:data_structure:binary_indexed_tree [2019/11/17] – [実装] 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]]
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