差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:binary_indexed_tree [2017/10/08] – ↷ programming:algorithm:data_structure:binary_indexed_tree から programming_algorithm:data_structure:binary_indexed_tree へページを移動しました。 ikatakos | programming_algorithm:data_structure:binary_indexed_tree [2019/11/01] – ikatakos | ||
|---|---|---|---|
| 行 12: | 行 12: | ||
| Binary Indexed Treeは、この2つを高速に行える。 | Binary Indexed Treeは、この2つを高速に行える。 | ||
| - | これだけ見ると「そんなシチュエーションあるの？」って感じだが、頭のいい人だと全然関係ないように見える問題をRSQに変換して効率的に解いたりしちゃうらしい。 | + | これだけ見ると「そんなのが何の役に立つの？」って感じだが、頭のいい人だと全然関係ないように見える問題を変換して効率的に解いたりしちゃうらしい。 |
| 詳しい説明は上のpdfで懇切丁寧に行われているので、Pythonコードだけメモ。 | 詳しい説明は上のpdfで懇切丁寧に行われているので、Pythonコードだけメモ。 | ||
| 行 44: | 行 44: | ||
| print(bit.sum(6) - bit.sum(3)) | print(bit.sum(6) - bit.sum(3)) | ||
| </ | </ | ||
| + | |||
| + | 注意点として、配列のindex等と異なり、添え字は1から始まる。そうしないと効率的に上下の要素を特定できないため。 | ||
| + | |||
| + | ８ | ||
| + | ４ | ||
| + | ２ ６ | ||
| + | １ ３ ５ ７ ９ ... | ||
| + | |||
| =====区間に対する更新===== | =====区間に対する更新===== | ||
| 行 88: | 行 96: | ||
| | | ||
| </ | </ | ||
| + | |||
| + | |||
| + | =====区間の最大値・最小値===== | ||
| + | |||
| + | 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:// | ||
| + | |||
| + | |||
| + | |||
