引用与vector

今天写线段树合并的时候，忽然想到可以用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扩容之后，引用和迭代器会失效。

here

虽然不清楚怎么快速拷贝区间的，但是貌似复杂度还是\(O(1)\)。

貌似拷贝区间还是\(O(n)\)，但是每次拷贝的区间长度会倍增（1.5倍或者是2倍），然后均摊下来的复杂度就是很小了。

参考资料：

一步步带你观察... by 老乐大魔王

vector中... by 智慧的人不要秃头