今天写线段树合并的时候，忽然想到可以用vector存树，这样就不用算空间了。
然后有了下面代码：
void modify(int& u,int l,int r,int p,int k) {
if (!u) u=newnode();
if (l==r) {
tr[u].max+=k;
tr[u].id=p;
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify(tr[u].ls,l,mid,p,k);
else modify(tr[u].rs,mid+1,r,p,k);
pushup(u);
}
看着很对，对吧？
但是这样子并不会将值更新到tr[u].ls和tr[u].rs。
然后经过数h的痛苦debug，有了如下测试代码：
int main() {
a.push_back(0);
cout<<a[0]<<' '<<&a[0]<<endl;
a.push_back(1);
cout<<a[0]<<' '<<&a[0]<<endl;
return 0;
}
原来是vector扩容之后，因为内部机制的关系，所有元素都会被拷贝到一个新地址。
然后此时的引用地址还是原来的，但是存的已经不是那个对应的元素了。
vector扩容之后，引用和迭代器会失效。
虽然不清楚怎么快速拷贝区间的，但是貌似复杂度还是\(O(1)\)。
貌似拷贝区间还是\(O(n)\)，但是每次拷贝的区间长度会倍增（1.5倍或者是2倍），然后均摊下来的复杂度就是很小了。
参考资料：
一步步带你观察... by 老乐大魔王
vector中... by 智慧的人不要秃头