永続的なセグメントツリーを作成しました。シミュレーションコンテストで主席ツリーを使用したのですが、私はこれまで書いたことがありませんでした。。。
当時の授業の印象を頼りに書きました、たくさんのブログを見ましたが理解できませんでした
概要#
変更操作があるたびに、変更が必要なノードをコピーし、新しくコピーしたノードで変更操作を行います。ここでの変更には、点と点の接続構造の変更も含まれます。そして、各バージョンの根ノードを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;
}
}
クエリ#
普通のセグメントツリーとほぼ同じ
非常に優雅に二つの関数に分けます。
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を打ち、クエリの際に新しいバージョンを作成する必要はありません。とても簡単です。。
また、このような長いデータ構造を書くと、ポインタで書く方が見栄えが良いと感じます。
ダブル経験#
P3834 【テンプレート】永続的なセグメントツリー 1（主席ツリー）
P3919 【テンプレート】永続的な配列（永続的なセグメントツリー / 平衡木）
私は全体的に二分 A を使って主席ツリーの問題を解いたので、ダブル経験はありませんでした。