前文我们讲了树状数组与线段树基本的实现，本文我们讲线段树的一些优化。

动态开点线段树

我们知道，如果使用二叉树实现，需要给线段树开大小为 4n4n 的数组。为了节省空间，我们可以不一次性建好树，而是在最初只建立一个根结点代表整个区间。当我们需要访问某个子区间时，才建立代表这个区间的子结点。我们用ls和rs记录儿子的编号。（结点只有在需要的时候才被创建）

时间复杂度仍为 O(log⁡n)O(\log n)

经过 mm 次操作后，节点的数量规模为 O(mlog⁡n)O(m\log n)，并且最多也只会创建 2n−12n-1 个节点，没有浪费。

区间修改

1
2
3
4
5
6
7
8
9
10
11
12
13
void modify(int& o,int l,int r){
    if(!o)o=++cnt;
    if(ql<=l&&r<=qr){
        t[o] += qk*(r-l+1);
        add[o] += qk;
        return;
    }
    pushdown(o,l,r);
    int mid = (l+r)>>1;
    if(ql<=mid)modify(ls[o],l,mid);
    if(qr>mid)modify(rs[o],mid+1,r);
    t[o] = t[rs[o]]+t[ls[o]];
}

区间查询

1
2
3
4
5
6
7
8
9
10
11
12
ll query(int o,int l,int r){
    if(!o)return 0;
    if(ql<=l&&r<=qr){
        return t[o];
    }
    pushdown(o,l,r);
    int mid = (l+r)>>1;
    ll ans=0;
    if(ql<=mid)ans+=query(ls[o],l,mid);
    if(qr>mid)ans+=query(rs[o],mid+1,r);
    return ans;
}

pushdown操作

1
2
3
4
5
6
7
8
9
10
11
12
void pushdown(int o,int l,int r){
    int mid = (l+r)>>1;
    if(!ls[o])ls[o]=++cnt;
    if(!rs[o])rs[o]=++cnt;
    int lch=ls[o],rch=rs[o];

    t[lch] += add[o] * (mid-l+1);
    t[rch] += add[o] * (r-mid);
    add[lch] += add[o];
    add[rch] += add[o];
    add[o]=0;
}

标记永久化

如果确定懒惰标记不会在中途被加到溢出（即超过了该类型数据所能表示的最大范围），那么就可以将标记永久化。标记永久化可以避免下传懒惰标记，只需在进行询问时把标记的影响加到答案当中，从而降低程序常数。具体如何处理与题目特性相关，需结合题目来写。

这样，在做查询时，只需增加一个变量，记录从根节点到当前节点的标记总和即可。

1
2
3
4
5
6
7
8
9
10
11
12
ll query(int o,int l,int r,ll lz){
    if(ql<=l&&r<=qr){
        return t[o] + lz*(r-l+1);
    }
    pushdown(o,l,r);
    int mid = (l+r)>>1;
    ll ans=0;
    int lch=o<<1,rch=(o<<1)|1;
    if(ql<=mid)ans+=query(lch,l,mid,lz+add[o]);
    if(qr>mid)ans+=query(rch,mid+1,r,lz+add[o]);
    return ans;
}