看本文文字部分可以少带脑子，但是代码部分仔细看了因为不一定编译了不一定对

动态开点

一般来说线段树的空间开销是比较巨大的，需要 \(4n\) 的空间，一般其实是可以支撑的，但是权值线段树就不一定了。值域级别的代价是支持不了的。

一般在动态开点的前提下只需要支持单点操作

一旦是序列问题还给定初始序列那就别老惦记你那动态开点了，用不了的（除非可持久化）

动态开点是怎么个事?

我们先铺垫一个小函数:newnode

int newnode(){return ++cnt;}

此处以单点赋值单点查询为例

int upd(int p,int l,int r,int x,int val){
	if(!p) p=newnode();
	if(l==r){
		tr[p].v=val;
	}
	else{
		int mid=(l+r)>>1;
		if(x<=mid){
			tr[p].lc=upd(tr[p].lc,l,mid,x,val);
		}
		else{
			tr[p].rc=upd(tr[p].rc,mid+1,r,x,val);
		}
	}
	return p;
}

霍等会，为啥要记录左右儿子？因为现在节点编号不再是父节点乘二而是另算的!

又等下，咋又变成int的函数了?因为你可能需要更改左右儿子的值而不是保持不变

我们类似的又可以写出查询的代码:

int ask(int p,int l,int r,int x){
	if(l==r){
		return tr[p].v;
	}
	int mid=(l+r)>>1;
	if(x<=mid) return ask(tr[p].lc,l,mid,x);
	else return ask(tr[p].rc,mid+1,r,x);
}

和普通的查询没点区别是吧，确实

类似的你也可以单点加区间查询和，但是一旦要打标记，这个动态开点就空间没咋优化还参数大了，一般不会用

大体其实没啥区别，要点就是编号方式不是堆式储存，在访问空节点时新建

标记永久化

有时候我们最喜欢的懒标记可能会太懒了一点，下传不好维护或者下传复杂度、不是 \(O(1)\)

咋办？那就让他懒死直接别动了

直接把pushup和pushdown一起扔掉

例子:线段树1

void build(int now,int l,int r){
	if(l==r){tr[now]=a[l];return;}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
    tr[now]=tr[ls]+tr[rs];
}

建树没啥区别，看看区间修改

void modify(int now,int l,int r,int L,int R,int k){
	if(L<=l and r<=R){
		tag[now]+=k;
		return ;
	}
	tr[now]+=(R-L+1)*k;
	int mid=(l+r)>>1;
	if(R<=mid){
		modify(ls,l,mid,L,R,k);
	}
	else if(L>mid){
		modify(rs,mid+1,r,L,R,k);
	}
	else{
		modify(ls,l,mid,L,mid,k);
		modify(rs,mid+1,r,mid+1,R,k);
	}
}

什么原理?

我们可以考虑对于某个区间的修改对结果的影响。因为我们没有要pushup，我们再向下递归的时候考虑每个区间需要被改动多少

如果目标区间完全被包含在当前区间内，加上目标区间长度*加几

向下递归时，如果目标区间完全在某个子树内，无疑直接递归下去

如果 \(mid\) 分开了目标区间，显然位于另一个子树的部分区间对于这个子树是没有贡献的

然后继续递归

int query(int now,int l,int r,int L,int R){
	int cnt=(R-L+1)*tag[now];
	if(L<=l and r<=R) return tr[now]+cnt;
	int mid=(l+r)>>1;
	if(R<=mid) cnt+=query(ls,l,mid,L,R);
	else if(L>mid) cnt+=query(rs,mid+1,r,L,R);
	else{
		cnt+=query(ls,l,mid,L,mid);
		cnt+=query(rs,mid+1,r,mid+1,R);
	}
	return cnt;
}

关于贡献的考虑略去，我们计算完正常的答案后要注意，当前答案要加上目标区间*当前tag，这是这一个节点的tag对答案的贡献

同时这里可以解释为什么上面要先判断当前区间和目标区间包含关系，因为tag对于答案的贡献要防止重复计算

然后就没了，这就是标记永久化

to be upd:可持久化，矩阵和标记，主席树