结构和思想


作用
常用来维护区间信息，可在 O(log2 (n)) 的时间复杂度内实现单点修改，区间修改，区间查询（区间求
和，区间最大值，区间最小值）等操作

线段树的基本结构（以区间加为例）
使用堆式存储结构，将每个长度不为 的区间划分为左右俩个区间递归求解，并通过合并左右俩个子区
间得到该区间信息

单点修改+区间查询

1

n个数：a1,a2,a3,…,an
q个操作：
1. 1 x d 修改ax=d
2. 2 l r 查询[l,r]最小值，并求出最小值出现了多少次

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5+10;
int n,q;
int a[N];   //原数组

struct info
{
    int minv,mincnt;  //记录最小值、最小值出现次数
};

info operator + (const info &l,const info &r)//重定义加法‘+’操作
{
    info a;
    a.minv=min(l.minv,r.minv);  //记录最小值
    //记录最小值出现次数
    if(l.minv==r.minv)   a.mincnt=l.mincnt+r.mincnt;
    else if(l.minv<r.minv)  a.mincnt=l.mincnt;
    else    a.mincnt=r.mincnt;
    return a;
}

struct node
{
    info val;
}seg[N*4];
// int minv[N*4];

void update(int id)   //更新
{
    seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

// [l,r]
void build(int id,int l,int r)
{
    if(l==r)
    {
        seg[id].val={a[l],1};   //权值是a[l],出现次数是1
    }
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);          //父节点为id，则左儿子id*2,右儿子id*2+1
        build(id*2+1,mid+1,r);
        update(id);     //更新
    }
}

//线段树当前节点为id，对应区间为[l,r],修改a[pos]->val
void change(int id,int l,int r,int pos,int val)   //单点修改
{
    if(l==r)    //到达叶子结点
    {
        seg[id].val={val,1};    //权值是val,出现次数是1
    }
    else
    {
        int mid=(l+r)/2;
        if(pos<=mid)    change(id*2,l,mid,pos,val);
        else    change(id*2+1,mid+1,r,pos,val);
        update(id);     //更新
    }
}

//[ql,qr]表示查询区间
info query(int id,int l,int r,int ql,int qr)
{
    if(l==ql && r==qr)  return seg[id].val;
    int mid=(l+r)/2;
    //[l,mid],[mid+1,r]
    if(qr<=mid)     return query(id*2,l,mid,ql,qr);
    else if(ql>mid)     return query(id*2+1,mid+1,r,ql,qr);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        return query(id*2,l,mid,ql,mid)+
                query(id*2+1,mid+1,r,mid+1,qr);
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)//修改a[x]->d
        {
            int x,d;
            scanf("%d%d",&x,&d);
            change(1,1,n,x,d);
        }
        else //查询[l,r]最小值
        {
            int l,r;
            scanf("%d%d",&l,&r);
            auto ans=query(1,1,n,l,r);
            printf("%d %d\n",ans.minv,ans.mincnt);
        }
    }
    return 0;
}

复杂的信息合并

2

n个数：a1,a2,a3,…,an
q个操作：
1. 1 x d 修改ax=d
2. 2 l r 查询[l,r]最大子段和，即从[l,r]中找到[l’,r’]，其数值之和最大

类似题目：

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5+10;
int n,q;
int a[N];   //原数组

struct info
{
    ll mss,mpre,msuf,s; //mss区间最大子段和，mpre最大前缀，psuf最大后缀，s区间和
    info (){}
    info(int a): mss(a),mpre(a),msuf(a),s(a) {} //最大子段和(初始化)
};

info operator + (const info &l,const info &r)//重定义加法‘+’操作
{
    info a;
    //维护信息！！！
    a.mss=max({l.mss,r.mss,l.msuf+r.mpre});
    a.mpre=max(l.mpre,l.s+r.mpre);
    a.msuf=max(r.msuf,r.s+l.msuf);
    a.s=l.s+r.s;
    return a;
}

struct node
{
    info val;
}seg[N*4];
// int minv[N*4];

void update(int id)   //更新
{
    seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

// [l,r]
void build(int id,int l,int r)
{
    if(l==r)
    {
        seg[id].val=info(a[l]);
    }
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);          //父节点为id，则左儿子id*2,右儿子id*2+1
        build(id*2+1,mid+1,r);
        update(id);     //更新
    }
}

//线段树当前节点为id，对应区间为[l,r],修改a[pos]->val
void change(int id,int l,int r,int pos,int val)   //单点修改
{
    if(l==r)    //到达叶子结点
    {
        seg[id].val=info(val);
    }
    else
    {
        int mid=(l+r)/2;
        if(pos<=mid)    change(id*2,l,mid,pos,val);
        else    change(id*2+1,mid+1,r,pos,val);
        update(id);     //更新
    }
}

//[ql,qr]表示查询区间
info query(int id,int l,int r,int ql,int qr)
{
    if(l==ql && r==qr)  return seg[id].val;
    int mid=(l+r)/2;
    //[l,mid],[mid+1,r]
    if(qr<=mid)     return query(id*2,l,mid,ql,qr);
    else if(ql>mid)     return query(id*2+1,mid+1,r,ql,qr);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        return query(id*2,l,mid,ql,mid)+
                query(id*2+1,mid+1,r,mid+1,qr);
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)//修改a[x]->d
        {
            int x,d;
            scanf("%d%d",&x,&d);
            change(1,1,n,x,d);
        }
        else //查询[l,r]最大值
        {
            int l,r;
            scanf("%d%d",&l,&r);
            auto ans=query(1,1,n,l,r);
            printf("%lld\n",ans.mss);
        }
    }
    return 0;
}

区间打标记以及下传

区间修改与区间查询

3

n个数：a1,a2,a3,…,an
q个操作：
1. 1 l r d 修改a[l~r]+=d
2. 2 l r 查询[l,r]最大a[i]

懒标记

懒标记就是一种延迟对节点的修改，每次修改时，仅修改极大的区间节点，并在这下节点增加懒标记，
若在遍历过程中遇到懒标记则将懒标记下传至子节点并修改子节点，若当前为叶子节点则不下传，回溯
过程合并左右儿子信息

标记永久化(不建议)

标记下传：

  1. 压标记，清空标记
  2. 打标记 (合并标记，更新信息)
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5+10;
int n,q;
int a[N];   //原数组

struct node
{
    ll t,val;
}seg[N*4];

void update(int id)   //更新数值
{
    seg[id].val=max(seg[id*2].val,seg[id*2+1].val);
}

void settag(int id,ll t)
{
    seg[id].val=seg[id].val+t;  //数值与标记相加
    seg[id].t=seg[id].t+t;  //标记合并
}

void pushdown(int id)   //下传标记
{
    if(seg[id].t != 0)    //标记非空
    {
        settag(id*2,seg[id].t);
        settag(id*2+1,seg[id].t);
        seg[id].t=0;
    }
}

void build(int id,int l,int r)
{
    if(l==r)
    {
        seg[id].val={a[l]};
    }
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);          //父节点为id，则左儿子id*2,右儿子id*2+1
        build(id*2+1,mid+1,r);
        update(id);     //更新
    }
}

//线段树当前节点为id，对应区间为[l,r]
void modify(int id,int l,int r,int ql,int qr,ll t)   //单点修改
{
    if(l==ql && r==qr)
    {
        settag(id,t);
        return;
    }
    int mid=(l+r)/2;
    pushdown(id);
    if(qr<=mid)     modify(id*2,l,mid,ql,qr,t);
    else if(ql>mid)     modify(id*2+1,mid+1,r,ql,qr,t);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        modify(id*2,l,mid,ql,mid,t);
        modify(id*2+1,mid+1,r,mid+1,qr,t);
    }
    update(id);    //更新
}

//[ql,qr]表示查询区间
ll query(int id,int l,int r,int ql,int qr)
{
    if(l==ql && r==qr)  return seg[id].val;
    int mid=(l+r)/2;
    //[l,mid],[mid+1,r]
    pushdown(id);
    if(qr<=mid)     return query(id*2,l,mid,ql,qr);
    else if(ql>mid)     return query(id*2+1,mid+1,r,ql,qr);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        return max(query(id*2,l,mid,ql,mid),
                query(id*2+1,mid+1,r,mid+1,qr));
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)
        {
            int l,r,d;
            scanf("%d%d%d",&l,&r,&d);
            modify(1,1,n,l,r,d);
        }
        else //查询[l,r]
        {
            int l,r;
            scanf("%d%d",&l,&r);
            auto ans=query(1,1,n,l,r);
            printf("%lld\n",ans);
        }
    }
    return 0;
}
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//封装版
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5+10;
int n,q;
int a[N];   //原数组

struct info //最大数值
{
    ll maxv;
};
struct tag  //标记
{
    ll add;
};

info operator + (const info &l,const info &r)//重定义加法‘+’操作：找最大数值
{
    return {max(l.maxv,r.maxv)};
}

info operator + (const info &v,const tag &t)//重定义加法‘+’操作:数值与标记相加
{
    return {v.maxv+t.add};
}

tag operator + (const tag &t1,const tag &t2)//重定义加法‘+’操作:标记合并
{
    return {t1.add+t2.add};
}

struct node   //封装
{
    tag t;
    info val;
}seg[N*4];

void update(int id)   //更新数值
{
    seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

void settag(int id,tag t)
{
    seg[id].val=seg[id].val+t;  //数值与标记相加
    seg[id].t=seg[id].t+t;  //标记合并
}

void pushdown(int id)   //下传标记
{
    if(seg[id].t.add != 0)    //标记非空
    {
        settag(id*2,seg[id].t);
        settag(id*2+1,seg[id].t);
        seg[id].t.add=0;
    }
}

void build(int id,int l,int r)
{
    if(l==r)
    {
        seg[id].val={a[l]};
    }
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);          //父节点为id，则左儿子id*2,右儿子id*2+1
        build(id*2+1,mid+1,r);
        update(id);     //更新
    }
}

//线段树当前节点为id，对应区间为[l,r]
void modify(int id,int l,int r,int ql,int qr,tag t)   //单点修改
{
    if(l==ql && r==qr)
    {
        settag(id,t);
        return;
    }
    int mid=(l+r)/2;
    pushdown(id);
    if(qr<=mid)     modify(id*2,l,mid,ql,qr,t);
    else if(ql>mid)     modify(id*2+1,mid+1,r,ql,qr,t);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        modify(id*2,l,mid,ql,mid,t);
        modify(id*2+1,mid+1,r,mid+1,qr,t);
    }
    update(id);    //更新
}

//[ql,qr]表示查询区间
info query(int id,int l,int r,int ql,int qr)
{
    if(l==ql && r==qr)  return seg[id].val;
    int mid=(l+r)/2;
    //[l,mid],[mid+1,r]
    pushdown(id);
    if(qr<=mid)     return query(id*2,l,mid,ql,qr);
    else if(ql>mid)     return query(id*2+1,mid+1,r,ql,qr);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        return query(id*2,l,mid,ql,mid)+
                query(id*2+1,mid+1,r,mid+1,qr);
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)
        {
            int l,r,d;
            scanf("%d%d%d",&l,&r,&d);
            modify(1,1,n,l,r,(tag){d});
        }
        else //查询[l,r]
        {
            int l,r;
            scanf("%d%d",&l,&r);
            auto ans=query(1,1,n,l,r);
            printf("%lld\n",ans.maxv);
        }
    }
    return 0;
}

4

luogu线段树1

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5+10;
int n,q;
int a[N];   //原数组

struct node
{
    ll t,val;
}seg[N*4];

void update(int id)   //更新数值
{
    seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

void settag(int id,ll t,int l,int r)
{
    seg[id].val=seg[id].val+t*(r-l+1);  //数值与标记相加
    seg[id].t=seg[id].t+t;  //标记合并
}

void pushdown(int id,int l,int r)   //下传标记
{
    if(seg[id].t != 0)    //标记非空
    {
        int mid=(l+r)/2;
        settag(id*2,seg[id].t,l,mid);
        settag(id*2+1,seg[id].t,mid+1,r);
        seg[id].t=0;
    }
}

void build(int id,int l,int r)
{
    if(l==r)
    {
        seg[id].val=a[l];
    }
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);          //父节点为id，则左儿子id*2,右儿子id*2+1
        build(id*2+1,mid+1,r);
        update(id);     //更新
    }
}

//线段树当前节点为id，对应区间为[l,r]
void modify(int id,int l,int r,int ql,int qr,ll t)   //修改
{
    if(l==ql && r==qr)
    {
        settag(id,t,l,r);
        return;
    }
    int mid=(l+r)/2;
    pushdown(id,l,r);
    if(qr<=mid)     modify(id*2,l,mid,ql,qr,t);
    else if(ql>mid)     modify(id*2+1,mid+1,r,ql,qr,t);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        modify(id*2,l,mid,ql,mid,t);
        modify(id*2+1,mid+1,r,mid+1,qr,t);
    }
    update(id);    //更新
}

//[ql,qr]表示查询区间
ll query(int id,int l,int r,int ql,int qr)
{
    if(l==ql && r==qr)  return seg[id].val;
    int mid=(l+r)/2;
    //[l,mid],[mid+1,r]
    pushdown(id,l,r);
    if(qr<=mid)     return query(id*2,l,mid,ql,qr);
    else if(ql>mid)     return query(id*2+1,mid+1,r,ql,qr);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        return query(id*2,l,mid,ql,mid)+
                query(id*2+1,mid+1,r,mid+1,qr);
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)
        {
            int l,r,d;
            scanf("%d%d%d",&l,&r,&d);
            modify(1,1,n,l,r,d);
        }
        else
        {
            int l,r;
            scanf("%d%d",&l,&r);
            auto ans=query(1,1,n,l,r);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

复杂的标记问题，标记的顺序

5

n个数：a1,a2,a3,…,an
q个操作：
1. 1 l r d 令a[lr]+d
2. 2 l r d 令a[lr]*d
3. 3 l r d 令a[lr]=d
4. 4 l r 查询 a[lr]之和mod(1e9+7)

分析：
a * 1 + d //区间加
a * d + 0 //区间乘
a * 0 + d //区间赋值

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5+10;
const ll mod = 1e9+7;
int n,q;
int a[N];   //原数组

struct tag  //标记
{
    ll mul,add;
};

tag operator + (const tag &t1,const tag &t2)//重定义加法‘+’操作:标记合并
{
    //有时间顺序 (a*t1.mul+t1.add)*t2.mul+t2.add
    return {t1.mul*t2.mul%mod,(t1.add*t2.mul+t2.add)%mod};
}

struct node   //封装
{
    tag t;
    ll val;
    int sz;     //表示有多少个数字
}seg[N*4];

void update(int id)   //更新数值
{
    seg[id].val=(seg[id*2].val+seg[id*2+1].val)%mod;
}

void settag(int id,tag t)
{
    seg[id].val=(seg[id].val*t.mul+seg[id].sz*t.add)%mod;  //数值与标记相加
    seg[id].t=seg[id].t+t;  //标记合并
}

void pushdown(int id)   //下传标记
{
    if(seg[id].t.mul !=1 || seg[id].t.add != 0)    //标记非空
    {
        settag(id*2,seg[id].t);
        settag(id*2+1,seg[id].t);
        seg[id].t.add=0;
        seg[id].t.mul=1;
    }
}

void build(int id,int l,int r)
{
    seg[id].t={1,0};
    seg[id].sz=r-l+1;   //此节点包含的 数据个数/叶子节点
    if(l==r)
    {
        seg[id].val={a[l]};
    }
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);          //父节点为id，则左儿子id*2,右儿子id*2+1
        build(id*2+1,mid+1,r);
        update(id);     //更新
    }
}

//线段树当前节点为id，对应区间为[l,r]
void modify(int id,int l,int r,int ql,int qr,tag t)
{
    if(l==ql && r==qr)
    {
        settag(id,t);
        return;
    }
    int mid=(l+r)/2;
    pushdown(id);
    if(qr<=mid)     modify(id*2,l,mid,ql,qr,t);
    else if(ql>mid)     modify(id*2+1,mid+1,r,ql,qr,t);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        modify(id*2,l,mid,ql,mid,t);
        modify(id*2+1,mid+1,r,mid+1,qr,t);
    }
    update(id);    //更新
}

//[ql,qr]表示查询区间
ll query(int id,int l,int r,int ql,int qr)
{
    if(l==ql && r==qr)  return seg[id].val;
    int mid=(l+r)/2;
    //[l,mid],[mid+1,r]
    pushdown(id);
    if(qr<=mid)     return query(id*2,l,mid,ql,qr);
    else if(ql>mid)     return query(id*2+1,mid+1,r,ql,qr);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        return (query(id*2,l,mid,ql,mid)+
                query(id*2+1,mid+1,r,mid+1,qr))%mod;
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty<=3)
        {
            int l,r,d;
            scanf("%d%d%d",&l,&r,&d);
            if(ty==1)   modify(1,1,n,l,r,(tag){1,d});   //区间加
            else if(ty==2)  modify(1,1,n,l,r,(tag){d,0});   //区间乘
            else    modify(1,1,n,l,r,(tag){0,d});   //区间赋值
           
        }
        else //查询[l,r]
        {
            int l,r;
            scanf("%d%d",&l,&r);
            auto ans=query(1,1,n,l,r);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

6

luogu线段树2

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
ll mod;
int n,q;
ll a[N];   //原数组

struct tag  //标记
{
    ll mul,add;
};

tag operator + (const tag &t1,const tag &t2)//重定义加法‘+’操作:标记合并
{
    //有时间顺序 (a*t1.mul+t1.add)*t2.mul+t2.add
    return {t1.mul*t2.mul%mod,(t1.add*t2.mul+t2.add)%mod};
}

struct node   //封装
{
    tag t;
    ll val;
    int sz;     //表示有多少个数字
}seg[N*4];

void update(int id)   //更新数值
{
    seg[id].val=(seg[id*2].val+seg[id*2+1].val)%mod;
}

void settag(int id,tag t)
{
    seg[id].val=(seg[id].val*t.mul+seg[id].sz*t.add)%mod;  //数值与标记相加
    seg[id].t=seg[id].t+t;  //标记合并
}

void pushdown(int id)   //下传标记
{
    if(seg[id].t.mul !=1 || seg[id].t.add != 0)    //标记非空
    {
        settag(id*2,seg[id].t);
        settag(id*2+1,seg[id].t);
        seg[id].t.add=0;
        seg[id].t.mul=1;
    }
}

void build(int id,int l,int r)
{
    seg[id].t={1,0};
    seg[id].sz=r-l+1;   //此节点包含的 数据个数/叶子节点
    if(l==r)
    {
        seg[id].val=a[l];
    }
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);          //父节点为id，则左儿子id*2,右儿子id*2+1
        build(id*2+1,mid+1,r);
        update(id);     //更新
    }
}

//线段树当前节点为id，对应区间为[l,r]
void modify(int id,int l,int r,int ql,int qr,tag t)
{
    if(l==ql && r==qr)
    {
        settag(id,t);
        return;
    }
    int mid=(l+r)/2;
    pushdown(id);
    if(qr<=mid)     modify(id*2,l,mid,ql,qr,t);
    else if(ql>mid)     modify(id*2+1,mid+1,r,ql,qr,t);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        modify(id*2,l,mid,ql,mid,t);
        modify(id*2+1,mid+1,r,mid+1,qr,t);
    }
    update(id);    //更新
}

//[ql,qr]表示查询区间
ll query(int id,int l,int r,int ql,int qr)
{
    if(l==ql && r==qr)  return seg[id].val;
    int mid=(l+r)/2;
    //[l,mid],[mid+1,r]
    pushdown(id);
    if(qr<=mid)     return query(id*2,l,mid,ql,qr);
    else if(ql>mid)     return query(id*2+1,mid+1,r,ql,qr);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        return (query(id*2,l,mid,ql,mid)+
                query(id*2+1,mid+1,r,mid+1,qr))%mod;
    }
}

int main()
{
    scanf("%d%d%d",&n,&q,&mod);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty<=2)
        {
            int l,r;
            ll d;
            scanf("%d%d%lld",&l,&r,&d);
            if(ty==1)   modify(1,1,n,l,r,(tag){d,0});  //区间乘
            else  modify(1,1,n,l,r,(tag){1,d});    //区间加
        }
        else //查询[l,r]
        {
            int l,r;
            scanf("%d%d",&l,&r);
            auto ans=query(1,1,n,l,r);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

线段树上二分

7

n个数：a1,a2,a3,…,an
q个操作：
1. 1 x d 修改ax=d
2. 2 l r d 查询最小i(l<=i<=r),使ai>=d; 若不存在则输出-1

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5+10;
int n,q;
int a[N];   //原数组

struct node
{
    int val;
}seg[N*4];
// int maxv[N*4];

void update(int id)   //更新
{
    seg[id].val=max(seg[id*2].val,seg[id*2+1].val);
}

// [l,r]
void build(int id,int l,int r)
{
    if(l==r)
    {
        seg[id].val=a[l];   //权值是a[l],出现次数是1
    }
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);          //父节点为id，则左儿子id*2,右儿子id*2+1
        build(id*2+1,mid+1,r);
        update(id);     //更新
    }
}

//线段树当前节点为id，对应区间为[l,r],修改a[pos]->val
void change(int id,int l,int r,int pos,int val)   //单点修改
{
    if(l==r)    //到达叶子结点
    {
        seg[id].val=val;    //权值是val,出现次数是1
    }
    else
    {
        int mid=(l+r)/2;
        if(pos<=mid)    change(id*2,l,mid,pos,val);
        else    change(id*2+1,mid+1,r,pos,val);
        update(id);     //更新
    }
}

//[ql,qr]表示查询区间
int search(int id,int l,int r,int ql,int qr,int d)
{
    if(l==ql && r==qr) 
    {
        if(seg[id].val<d)   return -1;
        else
        {
            if(l==r)    return l;
            int mid=(l+r)/2;
            if(seg[id*2].val>=d)    return search(id*2,l,mid,ql,mid,d);
            else    return search(id*2+1,mid+1,r,mid+1,qr,d);
        }
    }
    int mid=(l+r)/2;
    //[l,mid],[mid+1,r]
    if(qr<=mid)     return search(id*2,l,mid,ql,qr,d);
    else if(ql>mid)     return search(id*2+1,mid+1,r,ql,qr,d);
    else    //qr>mid,ql<=mid -> [ql.mid],[mid+1,qr]
    {
        int pos=search(id*2,l,mid,ql,mid,d);
        if(pos==-1)   return search(id*2+1,mid+1,r,mid+1,qr,d);
        else    return pos;
    }
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    for(int i=0;i<q;i++)
    {
        int ty;
        scanf("%d",&ty);
        if(ty==1)//修改a[x]->d
        {
            int x,d;
            scanf("%d%d",&x,&d);
            change(1,1,n,x,d);
        }
        else //查询[l,r]最大值
        {
            int l,r,d;
            scanf("%d%d%d",&l,&r,&d);
            auto ans=search(1,1,n,l,r,d);
            printf("%d\n",ans);
        }
    }
    return 0;
}

权值线段树

9

对值域进行线段树

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6+10;
int n,q;
int a[N];   //原数组

struct node
{
    int val;
}seg[N*2];

int read()  //快读
{ 
	#define gt getchar()
	#define isdi(a) (a>='0'&&a<='9')
	int x=0,sgn=1;char ch=gt;
	for(;!isdi(ch);ch=gt)if(ch=='-')sgn=-1;
	for(;isdi(ch);ch=gt)x=(x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

void update(int id)   //更新
{
    seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

// [l,r]
void build(int id,int l,int r)
{
    if(l==r)
    {
        seg[id].val=a[l];   //权值是a[l],出现次数是1
    }
    else
    {
        int mid=(l+r)/2;
        build(id*2,l,mid);          //父节点为id，则左儿子id*2,右儿子id*2+1
        build(id*2+1,mid+1,r);
        update(id);     //更新
    }
}

void add(int id,int l,int r,int val)
{
    if(l==r)    //到达叶子结点
    {
        if(l==val)   seg[id].val++;
    }
    else
    {
        int mid=(l+r)/2;
        if(val>mid)    add(id*2+1,mid+1,r,val);
        else    add(id*2,l,mid,val);
        seg[id].val++;
    }
    return;
}

void del(int id,int l,int r,int val)
{
    if(l==r)
    {
        if(seg[id].val) seg[id].val--;
        return;
    }
    if(val>seg[id].val) return; //大于整个节点，返回
    int mid=(l+r)/2;
    if(val>seg[id*2].val) del(id*2+1,mid+1,r,val-seg[id*2].val);//大于左子树，则去右子树
    else    del(id*2,l,mid,val);
//    else if(val<=seg[id*2].val) del(id*2,l,mid,val);    //找左子树
//    else return;
    seg[id].val--;
    return;
}

int find(int id,int l,int r)
{
    if(l==r) 
    {
        if(seg[id].val)   return l;
        return 0;
    }
    int mid=(l+r)/2;
    if(seg[id*2].val)  return find(id*2,l,mid);
    else               return find(id*2+1,mid+1,r);
    return 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    n=read();q=read();
    //scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        int temp;
        temp=read();
        //scanf("%d",&temp);
        a[temp]++;
    }
    build(1,1,n);
    for(int i=0;i<q;i++)
    {
        int k;
        k=read();
        //scanf("%d",&k);
        if(k<0)     del(1,1,n,-k);     //删去a[k]
        else        add(1,1,n,k);      //插入k
    }
    printf("%d\n",find(1,1,n));
    return 0;
}

9

权值线段树之字典树
异或第k小 (涉及 异或、字典树)
给n个数字：a1,a2,…,an
m个询问，每次给定两个数字x k，询问 a1 xor x, a2 xor x,…,an xor x 中从小到大排序中第k小的元素

1
2


扫描线与权值线段树

10

mex
有一个长度为n的数组a1,a2,…,an
回答q个询问，每次给一个区间[l,r],询问这个区间内最小没有出现的自然数

11[HDU3974]

Assign the task

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
//要写哭了 T-T
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e4+10;

struct node
{
    ll val;
}seg[N<<2];

void deer()
{
    int n;
    cin>>n;
    vector<int>vis(n+1),st(n+1),ed(n+1);
    vector<vector<int>> e(n+1);
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        e[v].push_back(u);
        vis[u]=1;
    }

    int cnt=0;
    auto dfs=[&](auto dfs,int x,int fa)->void
    {
        st[x]=++cnt;
        for(auto y:e[x])
        {
            if(y==fa)   continue;
            dfs(dfs,y,x);
        }
        ed[x]=cnt;
    };
    for(int i=1;i<=n;i++)
        if(!vis[i])   dfs(dfs,i,0);


    auto update = [&](int id)->void  //更新
    {
        if(seg[id].val!=-1)
        {
            seg[id<<1].val=seg[id<<1|1].val=seg[id].val;
            seg[id].val=-1;
        }
    };

    auto build = [&](auto build,int id,int l,int r)->void
    {
        seg[id].val=-1;
        if(l==r)    return;
        else
        {
            int mid=(l+r)/2;
            build(build,id*2,l,mid);      //父节点为id，则左儿子id*2,右儿子id*2+1
            build(build,id*2+1,mid+1,r);
        }
    };

    auto modify = [&](auto modify,int id,int ml,int mr,int l,int r,int y)->void   //区间修改
    {
        if(ml<=l && r<=mr)
        {
            seg[id].val=y;
            return;
        }
        update(id);
        int mid=(l+r)/2;
        if(ml<=mid) modify(modify,id<<1,ml,mr,l,mid,y);
        if(mid<mr)  modify(modify,id<<1|1,ml,mr,mid+1,r,y);
    };

    auto query = [&](auto query,int id,int q,int l,int r)->ll    //单点查询
    {
        if(l==r)  return seg[id].val;
        update(id);
        int mid=(l+r)/2;
        if(q<=mid)     return query(query,id*2,q,l,mid);
        else           return query(query,id*2+1,q,mid+1,r);
    };

    build(build,1,1,cnt);

    int q;
    cin>>q;
    while(q--)
    {
        char ty;
        cin>>ty;
        if(ty=='C')//单点查询
        {
            int x;
            cin>>x;
            cout<<query(query,1,st[x],1,cnt)<<"\n";
        }
        else //区间修改
        {
            int x;ll y;
            cin>>x>>y;
            modify(modify,1,st[x],ed[x],1,cnt,y);
        }
    }
    return;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cout<<"Case #"<<i<<":\n";
        deer();
    }
    return 0;
}
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//from repeater
//struct封装，struct构造函数
#include <bits/stdc++.h>

struct SegmentTree
{
	int n;
	std::vector<int> info;
	SegmentTree(int n) : n(n), info(n << 2, -1) {}

	void pushdown(int p)
	{
		if(info[p] != -1)
		{
			info[p << 1] = info[p << 1 | 1] = info[p];
			info[p] = -1;
		}
	}

	void build(int p, int l, int r)
	{
		if(l == r) return;
		int mid = (l + r) >> 1;
		build(p << 1, l, mid);
		build(p << 1 | 1, mid + 1, r);
	}

	void modify(int p, int L, int R, int l, int r, int k)
	{
		if(L <= l && r <= R)
		{
			info[p] = k;
			return;
		}

		pushdown(p);
		int mid = (l + r) >> 1;
		if(L <= mid) modify(p << 1, L, R, l, mid, k);
		if(mid < R) modify(p << 1 | 1, L, R, mid + 1, r, k);
	}

	int query(int p, int x, int l, int r)
	{
		if(l == r) return info[p];

		pushdown(p);
		int mid = (l + r) >> 1;
		if(x <= mid) return query(p << 1, x, l, mid);
		else return query(p << 1 | 1, x, mid + 1, r);
	}
};

void repeater()
{
	int n; std::cin >> n;
	std::vector<int> vis(n + 1), st(n + 1), ed(n + 1);
	std::vector<std::vector<int>> e(n + 1);
	for(int i = 1; i < n; i++)
	{
		int u, v; std::cin >> u >> v;
		e[v].emplace_back(u);
		vis[u] = 1;
	}

	int cnt = 0;
	auto dfs = [&](auto self, int x, int fa) -> void
	{
		st[x] = ++cnt;
		for(auto y : e[x])
		{
			if(y == fa) continue;
			self(self, y, x);
		}
		ed[x] = cnt;
	};
	for(int i = 1; i <= n; i++)
		if(!vis[i]) dfs(dfs, i, 0);

	SegmentTree segt(n);
	segt.build(1, 1, n);
	int m; std::cin >> m;
	while(m--)
	{
		char c; std::cin >> c;
		if(c == 'C')
		{
			int x; std::cin >> x;
			std::cout << segt.query(1, st[x], 1, n) << "\n";
		}
		else
		{
			int x, y; std::cin >> x >> y;
			segt.modify(1, st[x], ed[x], 1, n, y);
		}
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	int t; std::cin >> t;
	for(int i = 1; i <= t; i++)
	{
		std::cout << "Case #" << i << ":\n";
		repeater();
	}
	return 0;
}