线段树哲学-个人总结

· · Personal

线段树哲学

写完线段树读一遍有没有漏掉pushup和pushdown

建树方法

为了加快时间,我采用堆的方法,即点x的左儿子是x<<1 ,右儿子是x<<1|1,可能会牺牲一部分空间

这样空间复杂度就是O(kn),开数组的时候,最好开N<<3,最少开N<<2

对于build,我采用递归建树;每次查找时,将l,r作为参数传入给函数

对于pushup和pushdown

重要的哲学来了;

此哲学已变。

本人习惯:打上lazy标记表示,此区间内(包含此节点)的数据未更新

现在改了

正确时机:

修改时:

总结:直接返回要下放,查询子区间要下放,up前要将子区间的标记也下放

void update(int x, int l, int r, int ql, int qr, const Mat &k) {
    if (ql <= l && r <= qr) {
        lz[x] *= k; // 打上lazy标记
        down(x);// 立即下放标记
        return;
    }
    down(x);// 更新子区间前先下放标记
    gm;
    if (ql <= mid) update(ls, l, mid, ql, qr, k);
    else down(ls);
    if (mid < qr) update(rs, mid + 1, r, ql, qr, k);
    else down(rs);
    // 注意,因为之后要pushup,所以左右区间都要正确更新,即,每个区间如果不访问,要特地pushdown一下,这样pushup结果才能对;
    up(x);
}

注意,对于标记互相冲突(有先后顺序的标记),应该在进入节点时先pushdown一遍;

求解时:

总结:每个区间先pushdown,不用pushup

Mat query(int x, int l, int r, int ql, int qr) {
    down(x); // 先下放标记
    if (ql <= l && r <= qr) {
        return tre[x];
    }
    gm;
    Mat ret;
    if (ql <= mid) ret = query(ls, l, mid, ql, qr);
    if (mid < qr) ret += query(rs, mid + 1, r, ql, qr);
    // 查询子区间
    return ret;
}

对于区间修改,是直接覆盖lazy标记

别瞎用else!!!

对于区间乘法和加法,在下放标记时,要对子区间的加法标记乘上父区间的乘法标记

整体二分线段树写挂祭

修改时,先下方标记,再递归!

分清N,M!

pushdown判断数组越界时,不要搞混数组大小!

如果选择的是无脑pushdown,务必不要下放叶节点

线段树优化常数

当询问完全在一个区间时,直接return,不要再合并1次;

线段树判定当rs<M成立时,这个点不一定是叶子!