高度なアルゴリズム - バイナリインデックストリーとセグメントツリー
バイナリインデックストリー
単点更新、範囲照会が可能なデータ構造です。
典型的な問題として、数列の特定の位置を更新し、任意の区間の合計を求める操作が考えられます。
このデータ構造の核となるのがlowbit関数です。これは整数xに対して、xの最も右側にある1を含む部分を返す操作です。具体的にはx&-xと表現できます。
実装の基本となるのはtree配列です。各要素t ...
6月10日 23:11 投稿
奇想天外なアイデアがコードで現実になる場所
6月10日 23:11 投稿