我在尝试实现封装版本的动态开点线段树,但是出现了神秘的错误。错误部分的代码如下:
template<class Info, class Tag>
struct SegTree // 动态开点线段树
{
const int n; // 序列长度
int rt, tot; // 节点数量
vector<Info> info;
vector<Tag> tag;
vector<int> lson, rson;
SegTree(int _n): n(_n), rt(0), tot(0), info(1), tag(1), lson(100), rson(100) {}
void apply(int &id, const Tag &v, int l, int r)
{
// if(!id) newNode(id, l, r);
debug("In apply(before newNode): id = %d\n", id);
if(!id)
{
id = ++tot;
debug("id = %d, tot = %d\n", id, tot);
info.emplace_back(l, r);
tag.push_back(Tag());
lson.push_back(0), rson.push_back(0);
// lson.resize(id + 1, 0), rson.resize(id + 1, 0);
debug("lson.size() = %d, rson.size() = %d\n", (int)lson.size(), (int)rson.size());
d
debug("In apply: id = %d, [l, r] = [%d, %d]\n", id, l, r);
// tag[id].apply(v);
tag.at(id).apply(v);
// info[id].apply(v, l, r);
info.at(id).apply(v, l, r);
}
};
apply 是一个用于下放 tag 的函数,在此函数中,首先判定当前节点是否为空,如果为空(id == 0),那么就新建节点(使 id = ++tot,并使 tag,info,lson 和 rson 这几个 vector 扩容)。
在测试样例的过程中,当 id == 0 时,apply 函数出现了错误的反应:id 被设为了一个极大的不确定的值(比如 262406480)。输出中间变量发现,在 id = ++tot 这一行,id 确实被设为了正确的值,并且直到 tag.push_back(Tag()); 这一行仍是正确的。但执行了 lson.push_back(0), rson.push_back(0); 这一行之后,id 的值就被改变了。
后来我尝试在 SegTree 的构造函数中把 lson 和 rson 的大小设为 100,并把出错的那一行改为 lson.resize(id + 1, 0), rson.resize(id + 1, 0);,这时 id 的值就对了。**这个问题是不是 vector 扩容引起的?**如果是,应该如何规避?希望各位得到大佬的解答。
以下附上完整代码及测试样例时的输出:link