写了棵可持久化线段树，因为模拟赛里用到了主席树，而我却从来没写过。。。
凭借自己对当年上过的课的印象写的，因为翻了很多博客没看懂
概述
每当有修改操作时，把需要修改的节点复制一份，在新复制的节点上完成修改操作。这里的修改也包括对点与点连接结构的修改。然后将每个版本的根节点存入root数组。
结构
这棵线段树需要动态开点，所以要有struct
1
2
3
4
5
| struct node {
int l, r;
int ch[2];
int v;
} c[MAXN];
|
然后要有装初始元素的数组和root数组
1
| int a[MAXN], root[MAXN];
|
还要记录最新的节点和最新的版本
操作
所有操作中都要注意：递归操作之后newp会改变
建树
跟普通线段树差不多
要先将根节点的l,r初始化好
1
2
3
4
5
6
7
| 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;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void build (int p) {
if (c[p].l == c[p].r) {
c[p].v = a[c[p].l];
}
else {
++newp;
int son = 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;
}
}
|
查询
跟普通线段树差不多
非常优雅地分成两个函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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);
}
|
修改
跟普通线段树唯一不一样的地方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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过主席树那道了所以就没有双倍经验了嘤嘤嘤
