空间复杂度，一般是根据操作次数来计算的，或者按照题目的空间，算出最大开多少数组。
根据感性理解，线段树的深度是\(\lceil log_2n\rceil\)的，反正\(d = \lfloor log_2n\rfloor+1\)肯定够。
那\(m\)次操作，注意这个操作不一定是原题中的询问，而是你对于线段树的操作次数，总共就要开\(O(md)\)个点。
比如模板题操作次数就是\(4m\)（\(m\)为题目修改次数）。
然后就是这种写法：
int merge(int l,int r,int x,int y) {
if (!x||!y) return x+y;
int mid=l+r>>1;
if (l==r) {
tr[x].max+=tr[y].max;
if (!tr[x].max) tr[x].id=0;
else tr[x].id=l;
return x;
}
tr[x].ls=merge(l,mid,tr[x].ls,tr[y].ls);
tr[x].rs=merge(mid+1,r,tr[x].rs,tr[y].rs);
pushup(x);
return x;
}
是舍弃了原先的两棵线段树，此时只能保证x的信息是正确的，全部merge之后y的结构会改变。
但是本题中我们每次查的时候，只会查询根的值，这时为什么根的值也会变呢？
合理来说，根不会被挂到另外一个根上，所以应该是正确的。
对拍良久……终于发现如果\(u\)是\(v\)的父亲，\(u\)没有被修改过，那么\(u\)的根就是空，merge之后\(u\)的根会直接变成\(v\)的根，于是根节点的值就被改变了……
好坑……