我在尝试实现封装版本的动态开点线段树,但是出现了神秘的错误。错误部分的代码如下:
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