差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:binary_indexed_tree [2019/06/17] – ikatakos | programming_algorithm:data_structure:binary_indexed_tree [2019/11/07] – ikatakos | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ======Binary Indexed Tree====== | ======Binary Indexed Tree====== | ||
| + | |||
| + | =====概要===== | ||
| [[http:// | [[http:// | ||
| 行 13: | 行 15: | ||
| これだけ見ると「そんなのが何の役に立つの？」って感じだが、頭のいい人だと全然関係ないように見える問題を変換して効率的に解いたりしちゃうらしい。 | これだけ見ると「そんなのが何の役に立つの？」って感じだが、頭のいい人だと全然関係ないように見える問題を変換して効率的に解いたりしちゃうらしい。 | ||
| + | |||
| + | =====実装===== | ||
| 詳しい説明は上のpdfで懇切丁寧に行われているので、Pythonコードだけメモ。 | 詳しい説明は上のpdfで懇切丁寧に行われているので、Pythonコードだけメモ。 | ||
| 行 98: | 行 102: | ||
| + | =====区間の最大値・最小値===== | ||
| + | |||
| + | Segment Treeほどの柔軟性は無いが、いくらかの制約された条件下で、区間最大値・最小値の管理にも使える（以下は最大値の例） | ||
| + | |||
| + | * $update(i, x)$: $a_i$ を $x$ で更新する。この際、$x$ は必ず元の $a_i$ 以上でなければならない | ||
| + | * $getmax(i)$: | ||
| + | |||
| + | 単純に、上記のコードの加算を、MAXを取る操作に置きかえればよい。 | ||
| + | |||
| + | <sxh python> | ||
| + | class Bit: | ||
| + | def __init__(self, | ||
| + | self.size = n | ||
| + | self.tree = [0] * (n + 1) | ||
| + | |||
| + | def sum(self, i): | ||
| + | s = -(10 ** 18) # -INF | ||
| + | while i > 0: | ||
| + | s = max(s, self.tree[i]) | ||
| + | i -= i & -i | ||
| + | return s | ||
| + | |||
| + | def add(self, i, x): | ||
| + | while i <= self.size: | ||
| + | self.tree[i] = max(x, self.tree[i]) | ||
| + | i += i & -i | ||
| + | |||
| + | </ | ||
| + | |||
| + | 少し理解は難しくなるが、BITを2本使って管理することで、上記の制約を無くした区間最大値・最小値も得られる。 | ||
| + | |||
| + | * [[https:// | ||
| + | * [[https:// | ||
| + | |||
| + | ====累積和のlower bound==== | ||
| + | |||
| + | 累積和が $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 | ||
| + | </ | ||
