跳转至

线段树

普通懒标记线段树

支持区修区查，自定义标记和数据的类型，可以混搭其他多种模板。维护复杂的区间信息直接重载加法即可。

 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
61
62
63
64
65
66
namespace SegmentTree
{
    template<class Info,class Tag> struct SGT
    {
        int n;
        vector<Info> info;
        vector<Tag>  tag;
        SGT(int N=0):n(N) {}
        SGT(int N=0,Info Inf=Info()) {init(vector(N,Inf));}
        template<typename T> SGT(vector<T> a) {init(a);}
        template<typename T> inline void init(vector<T> ini)
        {
            n=ini.size()-1;
            info.assign(4<<__lg(n),Info()),tag.assign(4<<__lg(n),Tag());
            auto build=[&](auto build,int i,int l,int r)->void
            {
                if(l==r) return info[i]=ini[l],void();
                int mid=(l+r)>>1;
                build(build,i<<1,l,mid),build(build,i<<1|1,mid+1,r);
                pushup(i);
            };
            build(build,1,1,n);
        }
        inline void pushup(int i) {info[i]=info[i<<1]+info[i<<1|1];}
        inline void apply(int i,const Tag &tmp) {info[i].apply(tmp),tag[i].apply(tmp);}
        inline void pushdown(int i) {apply(i<<1,tag[i]),apply(i<<1|1,tag[i]),tag[i]=Tag();}
        void modify(int i,int l,int r,int L,int R,const Tag &tmp)
        {
            if(l>r) return;
            if(l<=L&&R<=r) return apply(i,tmp),void();
            pushdown(i);
            int mid=(L+R)>>1;
            if(l<=mid) modify(i<<1,l,r,L,mid,tmp);
            if(r>mid)  modify(i<<1|1,l,r,mid+1,R,tmp);
            pushup(i);
        }
        inline void modify(int l,int r,const Tag &tmp) {modify(1,l,r,1,n,tmp);}
        void cover(int i,int x,int L,int R,const Info &tmp)
        {
            if(L==R) return info[i]=tmp,void();
            pushdown(i);
            int mid=(L+R)>>1;
            if(x<=mid) cover(i<<1,x,L,mid,tmp);
            else cover(i<<1|1,x,mid+1,R,tmp);
            pushup(i);
        }
        inline void cover(int x,const Info &tmp) {cover(1,x,1,n,tmp);}
        Info query(int i,int l,int r,int L,int R)
        {
            if(R<l||r<L) return Info();
            if(l<=L&&R<=r) return info[i];
            pushdown(i);
            int mid=(L+R)>>1;
            return query(i<<1,l,r,L,mid)+query(i<<1|1,l,r,mid+1,R);
        }
        inline Info query(int l,int r) {return query(1,l,r,1,n);}
    };
    struct Tag
    {

    };
    struct Info
    {

    };
}