差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:binary_indexed_tree [2019/11/01] – ikatakos | programming_algorithm:data_structure:binary_indexed_tree [2019/11/19] – [累積和の二分探索] ikatakos | ||
|---|---|---|---|
| 行 51: | 行 51: | ||
| 注意点として、配列のindex等と異なり、添え字は1から始まる。そうしないと効率的に上下の要素を特定できないため。 | 注意点として、配列のindex等と異なり、添え字は1から始まる。そうしないと効率的に上下の要素を特定できないため。 | ||
| - | | + | ⇤←←←←←←８ |
| - | ４ | + | |
| - | ２ ６ | + | ⇤２ ⇤６ ⇤10 |
| - | １ ３ ５ ７ ９ ... | + | １ ３ ５ ７ ９ |
| 行 136: | 行 136: | ||
| * [[https:// | * [[https:// | ||
| + | =====累積和の二分探索===== | ||
| + | 二分探索により、累積和が $x$ のindexや、$x$ を越えない最大のindexとその時の累積和などを得ることができる。 | ||
| + | * [[https:// | ||
| + | <sxh python> | ||
| + | class Bit: | ||
| + | def __init__(self, | ||
| + | def sum(self, i): (略) | ||
| + | def add(self, i, x): (略) | ||
| + | def lower_bound(self, | ||
| + | """ | ||
| + | sum_ = 0 | ||
| + | pos = 0 | ||
| + | for i in range(self.depth, | ||
| + | k = pos + (1 << i) | ||
| + | if k <= self.size and sum_ + self.tree[k] < x: | ||
| + | sum_ += self.tree[k] | ||
| + | pos += 1 << i | ||
| + | return pos + 1, sum_ | ||
| + | </ | ||
