线段树模板

通过简单修改自定义内容，可实现区间加减乘除，max，min，取反以及其他功能，但暂时无法实现多操作（因为tag处理顺序不确定，要自己写）

对象 类型 说明
typename T 参数 线段树的数据类型
stduct node 内部 定义了l，r，v，tag
T dat[] 参数 线段树的原始序列
void pushup(int x) 内部 pushup
void build(int x,int l,int r) 函数 初始化，传入1,1,n
void pushdown(int x) 内部 pushdown
void update(int x,int L,int R,T v) 函数 更新，传入(1,l,r,v)
T query(int x,int L,int R) 函数 查询，传入(1,l,r)
T op(int x,int y) 自定义 pushup的操作符
T q_op(int x,int y) 自定义 query的操作符
T tot_init 自定义 query累计变量初始值
void apply(int x,T v) 自定义 修改单结点+打标记 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
template <typename T> struct SegmentTree{
    struct node{
        int l,r;
        T v,tag;
    }t[2000006*4];
    T dat[2000006];
    void pushup(int x){
        t[x].v=op(t[x*2].v,t[x*2+1].v);
    }
    void build(int x,int l,int r){
        t[x].l=l;
        t[x].r=r;
        if(l==r){
            t[x].v=dat[l];
            return;
        }
        int mid=(l+r)/2;
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
        pushup(x);
    }
    void pushdown(int x){
        if(t[x].tag&&t[x].l!=t[x].r){
            apply(x*2,t[x].tag);
            apply(x*2+1,t[x].tag);
            t[x].tag=0;
        }
    }
    void update(int x,int L,int R,T v){
        int l=t[x].l,r=t[x].r;
        if(L<=l&&r<=R){
            apply(x,v);
            return;
        }
        pushdown(x);
        int mid=(l+r)/2;
        if(L<=mid)update(x*2,L,R,v);
        if(mid+1<=R)update(x*2+1,L,R,v);
        pushup(x);
    }
    T query(int x,int L,int R){
        int l=t[x].l,r=t[x].r;
        if(L<=l&&r<=R){
            return t[x].v;
        }
        pushdown(x);
        int mid=(l+r)/2;
        T tot=tot_init;
        if(L<=mid)tot=q_op(tot,query(x*2,L,R));
        if(mid+1<=R)tot=q_op(tot,query(x*2+1,L,R));
        return tot;
    }
    ////////////////// 自定义函数区 ///////////////////
        T op(T x,T y){}/*操作运算符*/
        T q_op(T x,T y){}/*累计运算符*/
        T tot_init;/*query()累计变量初始值*/
        void apply(int x,T v){}/*修改单结点+打标记*/
    ////////////////// 自定义函数区 ///////////////////
};
SegmentTree<int>SegTree;

自定义函数用法：

1
2
3
4
5
6
7
8
9
10
区间加
    ////////////////// 自定义函数区 ///////////////////
        T op(T x,T y){return x+y;}
        T q_op(T x,T y){return x+y;}
        T tot_init=0;
        void apply(int x,T v){
            t[x].v+=(t[x].r-t[x].l+1)*v;
            t[x].tag+=v;
        }
    ////////////////// 自定义函数区 ///////////////////
1
2
3
4
5
6
7
8
9
10
区间减
    ////////////////// 自定义函数区 ///////////////////
        T op(T x,T y){return x+y;}
        T q_op(T x,T y){return x+y;}
        T tot_init=0;
        void apply(int x,T v){
            t[x].v-=(t[x].r-t[x].l+1)*v;
            t[x].tag-=v;
        }
    ////////////////// 自定义函数区 ///////////////////
1
2
3
4
5
6
7
8
9
10
区间乘
    ////////////////// 自定义函数区 ///////////////////
        T op(T x,T y){return x+y;}
        T q_op(T x,T y){return x+y;}
        T tot_init=1;
        void apply(int x,T v){
            t[x].v*=v;
            t[x].tag*=v;
        }
    ////////////////// 自定义函数区 ///////////////////
1
2
3
4
5
6
7
8
9
10
区间除
    ////////////////// 自定义函数区 ///////////////////
        T op(T x,T y){return x+y;}
        T q_op(T x,T y){return x+y;}
        T tot_init=1;
        void apply(int x,T v){
            t[x].v/=v;
            t[x].tag/=v;
        }
    ////////////////// 自定义函数区 ///////////////////
1
2
3
4
5
6
7
8
9
10
区间max
    ////////////////// 自定义函数区 ///////////////////
        T op(T x,T y){return max(x,y);}
        T q_op(T x,T y){return max(x,y);}
        T tot_init=0xcfcfcfcf;
        void apply(int x,T v){
            t[x].v=v;
            t[x].tag=v;
        }
    ////////////////// 自定义函数区 ///////////////////
1
2
3
4
5
6
7
8
9
10
区间min
    ////////////////// 自定义函数区 ///////////////////
        T op(T x,T y){return min(x,y);}
        T q_op(T x,T y){return min(x,y);}
        T tot_init=0x3f3f3f3f;
        void apply(int x,T v){
            t[x].v=v;
            t[x].tag=v;
        }
    ////////////////// 自定义函数区 ///////////////////
1
2
3
4
5
6
7
8
9
10
11
区间取反（update时v传入1即可）
    ////////////////// 自定义函数区 ///////////////////
        T op(T x,T y){return x+y;}/*操作运算符*/
        T q_op(T x,T y){return x+y;}/*累计运算符*/
        T tot_init=0;/*query()累计变量初始值*/
        void apply(int x,T v){
			t[x].v=(t[x].r-t[x].l+1)-t[x].v;
			t[x].tag=!t[x].tag;
		}/*修改单结点+打标记*/
    ////////////////// 自定义函数区 ///////////////////

单行压缩版

1
2
3
4
5
6
7
8
9
template <typename T> struct SegmentTree{struct node{int l,r;T v,tag;}t[2000006*4];T dat[2000006];void pushup(int x){t[x].v=op(t[x*2].v,t[x*2+1].v);}void build(int x,int l,int r){t[x].l=l;t[x].r=r;if(l==r){t[x].v=dat[l];return;}int mid=(l+r)/2;build(x*2,l,mid);build(x*2+1,mid+1,r);pushup(x);}void pushdown(int x){if(t[x].tag&&t[x].l!=t[x].r){apply(x*2,t[x].tag);apply(x*2+1,t[x].tag);t[x].tag=0;}}void update(int x,int L,int R,T v){int l=t[x].l,r=t[x].r;if(L<=l&&r<=R){apply(x,v);return;}pushdown(x);int mid=(l+r)/2;if(L<=mid)update(x*2,L,R,v);if(mid+1<=R)update(x*2+1,L,R,v);pushup(x);}T query(int x,int L,int R){int l=t[x].l,r=t[x].r;if(L<=l&&r<=R){return t[x].v;}pushdown(x);int mid=(l+r)/2;T tot=tot_init;if(L<=mid)tot=q_op(tot,query(x*2,L,R));if(mid+1<=R)tot=q_op(tot,query(x*2+1,L,R));return tot;}
    ////////////////// 自定义函数区 ///////////////////
        T op(T x,T y){}/*操作运算符*/
        T q_op(T x,T y){}/*累计运算符*/
        T tot_init;/*query()累计变量初始值*/
        void apply(int x,T v){}/*修改单结点+打标记*/
    ////////////////// 自定义函数区 ///////////////////
};
SegmentTree<int>SegTree;

一~行~坨区间和

1
template <typename T> struct SegmentTree{struct node{int l,r;T v,tag;}t[2000006*4];T dat[2000006];void pushup(int x){t[x].v=op(t[x*2].v,t[x*2+1].v);}void build(int x,int l,int r){t[x].l=l;t[x].r=r;if(l==r){t[x].v=dat[l];return;}int mid=(l+r)/2;build(x*2,l,mid);build(x*2+1,mid+1,r);pushup(x);}void pushdown(int x){if(t[x].tag&&t[x].l!=t[x].r){apply(x*2,t[x].tag);apply(x*2+1,t[x].tag);t[x].tag=0;}}void update(int x,int L,int R,T v){int l=t[x].l,r=t[x].r;if(L<=l&&r<=R){apply(x,v);return;}pushdown(x);int mid=(l+r)/2;if(L<=mid)update(x*2,L,R,v);if(mid+1<=R)update(x*2+1,L,R,v);pushup(x);}T query(int x,int L,int R){int l=t[x].l,r=t[x].r;if(L<=l&&r<=R){return t[x].v;}pushdown(x);int mid=(l+r)/2;T tot=tot_init;if(L<=mid)tot=q_op(tot,query(x*2,L,R));if(mid+1<=R)tot=q_op(tot,query(x*2+1,L,R));return tot;}T op(T x,T y){return x+y;}T q_op(T x,T y){return x+y;}T tot_init=0;void apply(int x,T v){t[x].v+=(t[x].r-t[x].l+1)*v;t[x].tag+=v;}};
#算法
线段树模板
http://shicj.pages.dev/2024/08/12/线段树模板/
作者
shicj
发布于
2024年8月12日
许可协议