差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン |
programming_algorithm:data_structure:binary_indexed_tree [2019/11/07] – ikatakos | programming_algorithm:data_structure:binary_indexed_tree [2019/11/08] – [累積和のlower bound] ikatakos |
---|
* [[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]] |