Alan_Zhao @ 2021-06-27 19:55:32
题解里的线段树合并全都长这样：
int merge(int x,int y,int tl,int tr) {
if(x==0||y==0) return x|y;
if(tl==tr) {
int now=++tot;
tree[now].num=tree[x].num+tree[y].num;
return now;
}
int mid=(tl+tr)/2,now=++tot;
tree[now].ls=merge(tree[x].ls,tree[y].ls,tl,mid);
tree[now].rs=merge(tree[x].rs,tree[y].rs,mid+1,tr);
up(now);
return now;
}或这样：
int merge(int u,int v,int l,int r)
{
if(!u||!v)return u|v;
int mid=l+r>>1,x=++tot;
t[x].siz=t[u].siz+t[v].siz;
t[x].lc=merge(t[u].lc,t[v].lc,l, mid );
t[x].rc=merge(t[u].rc,t[v].rc,mid+1,r);
return x;
}它们在有一个点为空的时候，都直接返回了另一个点。这样为啥是对的？感觉父节点进行更新的时候有可能会影响到子节点的线段树。
by Alan_Zhao @ 2021-06-27 19:56:54
有一篇题解解释说：
但是x线段树递归到某个空子树的时候，还是要把y上对应的子树拿过来，这可以相当于是打标记，暂时用了y的子树。正经合并的时候肯定是不能改变y的信息了。
但我不明白这哪里打标记了。。。
by 南门阳德 @ 2021-06-27 20:01:09
父节点在合并之后不是就不会再更改了吗
by Alan_Zhao @ 2021-06-27 20:05:35
@南门阳德 也有题解把更改放在合并后面，也能过
by linfourxu @ 2021-06-27 20:07:57
@Alan_Zhao 如果每颗线段树都完全独立的话时空复杂度是不可能对的。
by 南门阳德 @ 2021-06-27 20:09:01
如果其他儿子再向这里合并不就新开节点了吗
by 南门阳德 @ 2021-06-27 20:09:38
或者再更改
by 南门阳德 @ 2021-06-27 20:10:21
只有在不影响儿子的前提下才会直接使用儿子的节点啊。
by linfourxu @ 2021-06-27 20:10:23
@Alan_Zhao 当一个节点已经跟他父亲合并时，他的使命就已经结束了，有关他的询问就已经处理好了。
by Alan_Zhao @ 2021-06-27 20:12:29
@linfourxu 好像不是的，题解里全是在线做法
by 南门阳德 @ 2021-06-27 20:13:18
@linfourxu 这个倒不太正确吧，毕竟这个题不能直接存答案，必须在线段树上差。