主席木を使った模擬試合で使うために、可持久化線段木を書いたことがありますが、実は一度も書いたことがありませんでした...
当時の授業の印象に基づいて書いたので、たくさんのブログを見ても理解できませんでした
概要#
変更操作があるたびに、変更するノードをコピーして、新しいコピーされたノードで変更操作を行います。ここでの変更には、点と点の接続構造の変更も含まれます。そして、各バージョンのルートノードをroot配列に保存します。
構造#
この線段木は動的にノードを作成する必要があるため、structが必要です。
struct node {
int l, r; // 対応する区間
int ch[2]; // 0:左の子、1:右の子
int v; // 値
} c[MAXN];
そして、初期要素を格納する配列とroot配列が必要です。
int a[MAXN], root[MAXN];
また、最新のノードと最新のバージョンを記録する必要があります。
int newp, newv;
操作#
すべての操作で注意する必要があります：再帰操作の後、newpが変更されることに注意してください。
木の構築#
通常の線段木とほぼ同じです。
まず、ルートノードのlとrを初期化する必要があります。
root[++newv] = ++newp;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
c[newp].l = 1;
c[newp].r = n;
void build (int p) {
if (c[p].l == c[p].r) {
c[p].v = a[c[p].l];
}
else {
++newp;
int son = newp; // 現在のノードを保存します。newpが変化した後は使用できません
c[son].l = c[p].l;
c[son].r = (c[p].l + c[p].r) >> 1;
c[p].ch[0] = son;
build(son);
c[p].v += c[son].v;
++newp;
son = newp;
c[son].l = ((c[p].l + c[p].r) >> 1) + 1;
c[son].r = c[p].r;
c[p].ch[1] = son;
build(son);
c[p].v += c[son].v;
}
}
クエリ#
通常の線段木とほぼ同じです
非常にエレガントに2 つの関数に分けます
int rq(int p, int l, int r) {
if (c[p].l >= l && c[p].r <= r) { // 完全に範囲内にある場合
return c[p].v;
}
else if (c[p].r < l || c[p].l > r) { // 完全に範囲外にある場合
return 0;
}
else {
int s = 0;
s += rq(c[p].ch[0], l, r);
s += rq(c[p].ch[1], l, r);
return s;
}
}
int query (int v, int l, int r) {
return rq(root[v], l, r);
}
変更#
通常の線段木と唯一の違い
int ra (int p, int x, int k) { // 返り値：現在のバージョンで変更後に作成されたノード
if (c[p].l == c[p].r && c[p].l == x) {
c[++newp] = c[p];
c[newp].v += k;
return newp;
}
else {
if (c[p].r < x || c[p].l > x) return p; // 変更がない場合は元のノードを使用します
else {
int son = ++newp;
c[son] = c[p];
c[son].ch[0] = ra(c[p].ch[0], x, k); // 自分の子を更新します
c[son].ch[1] = ra(c[p].ch[1], x, k);
c[son].v = c[c[son].ch[0]].v + c[c[son].ch[1]].v;
return son;
}
}
}
void add (int v, int x, int k) {
int p = root[v];
root[++newv] = ra(p, x, k); // 新しいバージョンのルートノード
}
その他#
しかし、これでは区間の変更はできません。
しかし、そのテンプレート問題では必要ありません
区間の変更が必要な場合は、通常どおりlazytagを使用し、クエリのときも新しいバージョンを作成する必要はありません。とても簡単です...
また、このような長いデータ構造を書くたびに、ポインタを使用すると見栄えが良くなると感じます。
2 倍の経験#
P3834 【模板】可持久化線段木 1（主席木）
P3919 【模板】可持久化配列（可持久化線段木 / 平衡木）
主席木の問題を整体二分法で解いたので、2 倍の経験はありませんでした、嘤嘤嘤