寫了棵可持久化線段樹，因為模擬賽裡用到了主席樹，而我卻從來沒寫過。。。
憑藉自己對當年上過的課的印象寫的，因為翻了很多博客沒看懂
概述#
每當有修改操作時，把需要修改的節點複製一份，在新複製的節點上完成修改操作。這裡的修改也包括對點與點連接結構的修改。然後將每個版本的根節點存入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 過主席樹那道了所以就沒有雙倍經驗了嘤嘤嘤