セグメント木
構築に$ O(N)かかる。
区間に対するクエリに$ O(logN)の速さで処理できるやつ。 区間の〇〇を扱いたい時は使える。モノイド辺りだと使える。
多分「結合則」とやらを満たしていれば、単位元を自作すれば載せることができる。
そういえば結合則満たしてたらダブリングとかできたよね…？（曖昧）
自分がやったこと
メモ
セグメント木は基本的に
構築
更新
検索
の３つの段階からなる。
コツ
セグ木(0-indexed)を頭にいつも入れておこう
横幅をn、自分のいるindexをiとする
サイズ…$ 2^n-1。
たとえばn=8のとき、下から要素数を足していくと$ 8+4+2+1になる。此れ即ち$ 1111_{(2)}。なので、$ 1000_{(2)}×2 - 1 = 10000_{(2)} -1 = 1111_{(2)} ということ。
最下段…(n-1)+0からn回ループ
親…(i-1)/2
子…i*2+1とi*2+2
https://gyazo.com/8d2d15e3bd6ecd30e1868944079bb216
書き方
private
最下段の長さをもつint nと、セグツリー用のvector<int> v;
public
コンストラクタ
長さnは、元の配列の長さを超える2冪の数(whileで実装)
node.resize(n*2-1,初期値)でセグ木初期化
最下段をn-1からn回ループで埋めていく
n-2から0まで、子を比較しながら上る
update(i,val)
最下段を更新
親に上りながら更新していく
getmin(a,b, now = 0, l = 0, r = -1)
再帰的に求める
もし全く[a,b)と[l,r)が重なってない→一番弱い値(min比較だとINFを返す)
すっぽり入ってる→返す
多分そう部分的にそう→子を比較(再帰)して返す
イメージ
https://gyazo.com/de9720e5fc613595a7131e88cb6d2b3f
code:segmenttree(適当).cpp
// vector<int>を渡してあげると、それを元にセグメント木を構築する。
struct SegmentTree {
int n; // 最下段のノード数
vector<int> node;
int SIJK; // 最弱なやつ(INFとか-1とか)
public:
SegmentTree(vector<int> v) {
SIJK = (1ll << 31) - 1; // INFは最弱なので
int sz = v.size();
n = 1;
while (n < sz) n *= 2; // n…最下段の横幅
node.resize(2 * n - 1, SIJK);
// 最下段に突っ込む
// 最下段以外を更新していく
for (int i = n - 2; i >= 0; i--) {
}
}
// 結合法則を満たすやつならなんでもいいよー。aかbを返す。
int compare(int a, int b) {
return min(a, b);
}
// i番目の要素をvalに変更する
void update(int i, int val) {
// まず最下段(2n-1)を変更する
i += n - 1;
// 上に行きながら更新していく
while (i > 0) {
i = (i - 1) / 2; // 親へ
}
}
// [a,b) 中の結果を返す。[l,r)は対称区間の左端と右端。
int find(int a, int b, int now = 0, int l = 0, int r = -1) {
// 初期化
if (r < 0) r = n;
// 俺は関係ないとき -> 答えの邪魔にならない値を返す
if (r <= a || b <= l) return SIJK;
// 要求区間の中にノードがすっぽり入ってる → 計算候補として返す
if (a <= l && r <= b) return nodenow; // ノードの一部分だけ要求区間に入ってる → 子を再帰的に探索する
int vl = find(a, b, 2 * now + 1, l, (l + r) / 2); // 子(左)
int vr = find(a, b, 2 * now + 2, (l + r) / 2, r); // 子(右)
return compare(vl, vr);
}
};