线段树

发表于 分类于

与树状数组类似，线段树同样可以高效率对区间进行查询、更新操作。与树状数组不同的是，树状数组仅限于计算前缀和，应用问题存在很大的局限。所以通常用线段树来维护一系列区间操作，特别是区间最大值最小值问题。

表示区间[1, 10]的线段树表示如下：

每个节点维护对应区间的信息,某节点的区间为其左右孩子节点区间之和。

单点更新和区间查询

以下以结构体形式来构建线段树

1
2
3
4
5
6
7
int a[maxn]
struct Node{
    int l,r;
    int val;
    int sum;
};
Node seg[maxn*3];

每个节点维护对应区间的最大值$val$，区间和$sum$，$l$为区间左端点，$r$为区间右端点。

可以证明得到，线段树节点总数不超过叶结点总数的2倍，线段树数组通常设置为维护数组(即叶结点对应的值)的3倍。

以求区间最值和求区间和为例，构建线段树的操作为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void build(int i,int l,int r){
    seg[i].l=l;
    seg[i].r=r;
    if(l==r){
        seg[i].sum=a[l];
        seg[i].val=a[l];
        return;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
    seg[i].val=min(seg[2*i].val,seg[2*i+1].val);
    seg[i].sum=seg[2*i].sum+seg[2*i+1].sum;
}
build(1,1,n);

其中$i$为二叉线段树中节点的编号，$l$为区间左端点，$r$为区间右端点。节点$i$的左孩子为节点$2i$，节点$i$的右孩子为节点$2i+1$。

在构建节点左右子树后，再更新当前节点对应的区间最值和区间和。

更新线段树的操作为

1
2
3
4
5
6
7
8
9
10
11
12
void update(int i,int k,int x){
    if(seg[i].l==seg[i].r){
        seg[i].val=x;
        return;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(k<=mid) update(2*i,k,x);
    else update(2*i+1,k,x);
    seg[i].sum=seg[2*i].sum+seg[2*i+1].sum;
    seg[i].val=min(seg[2*i].val,seg[2*i+1].val);
}
update(1,pos,x);

更新操作在线段树的节点中维护，并不需要更新原有数组，原有数组信息仅在构建线段树的时候用到。

求区间和操作如下：

1
2
3
4
5
6
7
8
9
10
int sum(int i,int l,int r){
    if(l<=seg[i].l&&seg[i].r<=seg[i].r){
        return seg[i].sum;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    int suml=0,sumr=0;
    if(l<=mid) suml=sum(2*i,l,r);
    if(r>mid) sumr=sum(2*i+1,l,r);
    return suml+sumr;
}

也可以这么写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sum(int i,int l,int r){
    if(l==seg[i].l&&seg[i].r==r){
        return seg[i].sum;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    int ans=0;
    if(r<=mid) ans=sum(2*i,l,r);
    else if(l>mid) ans=sum(2*i+1,l,r);
    else{
        ans+=sum(2*i,l,mid);
        ans+=sum(2*i+1,mid+1,r);
    }
    return ans;
}

区间和操作应用树状数组同样可以高效查询、更新。

查询区间最小值的操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int query(int i,int l,int r){
    if(l<=seg[i].l&&seg[i].r<=r){
        return seg[i].val;
    }
    int minl=inf,minr=inf;
    int mid=(seg[i].l+seg[i].r)/2;
    if(l<=mid){
        minl=query(2*i,l,r);
    }
    if(r>mid){
        minr=query(2*i+1,l,r);
    }
    return min(minl,minr);
}

POJ 3264

求给定区间的最大值和最小值的差值，区间查询，没有更新操作，为静态查询。

由于查询返回应同时返回区间最小值和区间最大值，可以将区间最小值ans1,区间最大值ans2设为全局变量，在每次查询的时候更新，也可以返回将区间的最大值、最小值这两个参数以pair类型返回，会麻烦很多。

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=200005;
const int inf=0x3f3f3f3f;
struct Node{
    int l,r;
    int val1,val2;
};
int ans1,ans2;
int a[maxn];
Node seg[maxn*3];
void build(int i,int l,int r){
    seg[i].l=l;
    seg[i].r=r;
    if(l==r){
        seg[i].val1=seg[i].val2=a[l];
        return;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
    seg[i].val1=min(seg[2*i].val1,seg[2*i+1].val1);
    seg[i].val2=max(seg[2*i].val2,seg[2*i+1].val2);
}
void query(int i,int l,int r){
    if(seg[i].val2<=ans2&&seg[i].val1>=ans1) return;
    if(seg[i].l==l&&seg[i].r==r){
        ans1=min(seg[i].val1,ans1);
        ans2=max(seg[i].val2,ans2);
        return;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(r<=mid) query(2*i,l,r);
    else if(l>mid) query(2*i+1,l,r);
    else{
        query(2*i,l,mid);
        query(2*i+1,mid+1,r);
    }
}

int main()
{
    int n,q;
    while(scanf("%d%d",&n,&q)==2){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        build(1,1,n);
        for(int i=1;i<=q;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            ans1=inf,ans2=-inf;
            query(1,l,r);
            printf("%d\n",ans2-ans1);
        }
    }
    return 0;
}

hdu 1754

区间查询，查询区间最大值，更新操作更新单点的值。

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
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200005;
struct Node{
    int l,r;
    int val;
};
Node seg[maxn*3];
int a[maxn];
void build(int i,int l,int r){
    seg[i].l=l;
    seg[i].r=r;
    if(l==r) seg[i].val=a[l];
    else{
         int mid=(l+r)/2;
         build(2*i,l,mid);
         build(2*i+1,mid+1,r);
         seg[i].val=max(seg[2*i].val,seg[2*i+1].val);
    }
}
int query(int i,int l,int r){
    if(l<=seg[i].l&&seg[i].r<=r){
        return seg[i].val;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(r<=mid) return query(2*i,l,r);
    else if(l>mid) return query(2*i+1,l,r);
    else return max(query(2*i,l,r),query(2*i+1,l,r));
}
void update(int i,int k,int x){
    if(seg[i].l==k&&seg[i].r==k){
        seg[i].val=x;
        return;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(k<=mid) update(2*i,k,x);
    else update(2*i+1,k,x);
    seg[i].val=max(seg[2*i].val,seg[2*i+1].val);
}
int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)==2){
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        build(1,1,n);
        while(m--){
            char op[2];
            int x,y;
            scanf("%s%d%d", op,&x,&y);
            if (op[0]=='Q'){
                int ans=query(1,x,y);
                printf("%d\n", ans);
            }
            else{
                update(1,x,y);
            }
        }
    }
    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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=200005;
int val[maxn*3];
void build(int i,int l,int r){
    if(l==r){
        scanf("%d",&val[i]);
        return;
    }
    int mid=(l+r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
    val[i]=max(val[2*i],val[2*i+1]);
}
void update(int i,int l,int r,int k,int x){
    if(l==k&&r==k){
        val[i]=x;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) update(2*i,l,mid,k,x);
    else update(2*i+1,mid+1,r,k,x);
    val[i]=max(val[2*i],val[2*i+1]);
}
int query(int i,int l,int r,int x,int y){
    if(x<=l&&r<=y) return val[i];
    int mid=(l+r)/2,res=0;
    if(x<=mid) res=max(res,query(2*i,l,mid,x,y));
    if(y>mid) res=max(res,query(2*i+1,mid+1,r,x,y));
    return res;
}
int main()
{
   int n,m;
   while (scanf("%d%d",&n,&m)==2){
        build(1,1,n);
        while(m--){
            char op[2];
            int x,y;
            scanf("%s%d%d", op,&x,&y);
            if (op[0]=='Q'){
                int ans=query(1,1,n,x,y);
                printf("%d\n", ans);
            }
            else{
                update(1,1,n,x,y);
            }
        }
    }
	return 0;
}

区间更新和单点查询

树状数组通过差分思想来更新区间和查询单点，线段树则通过延迟标记来批量标记节点所对应的子区间。

延迟标记表示该节点$i$所对应的区间$[l,r]$同时执行了某个更新操作，比如同时赋值为某个值$x$。如此一来，不必每次更新操作都更新到$[l,r]$区间的叶子节点。

在查询区间或者更新区间仅仅涉及节点$i$的部分区间时，将延迟标记下放到节点的左孩子$2i$和右孩子$2i+1$对应的区间，同时将当前节点$i$的延迟标记清空。

区间染色问题

hdu 3974

线段树维护dfs序，以邻接表形式来表示图，从根节点dfs，记录dfs过程中每个节点的dfs开始时间和结束时间，作为线段树中的次序。每个节点对应的下属必然是dfs中连续的一段区间，所以每次分配任务的时候对该节点dfs开始时间到dfs结束时间内的节点更新即可，为区间更新。每次查询查询点对应的任务值，为单点更新操作。

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=50005;
struct Edge{
    int to,next;
};
Edge edge[maxn];
int head[maxn],tot;
int cnt;
int start[maxn],en[maxn];
int vis[maxn];
void init()
{
    cnt=0;
    tot=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
    edge[tot].to=v;
    edge[tot].next=head[u];
    head[u]=tot++;
}
void dfs(int u)
{
    ++cnt;
    start[u]=cnt;
    for(int i=head[u];i!=-1;i=edge[i].next){
        dfs(edge[i].to);
    }
    en[u]=cnt;
}
struct Node{
    int l,r;
    int lazy;
    int val;
};
Node seg[maxn*4];
void build(int i,int l,int r){
    seg[i].l=l;
    seg[i].r=r;
    seg[i].val=-1;
    seg[i].lazy=0;
    if(l==r) return;
    int mid=(l+r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
}
void update(int i,int l,int r,int v){
    if(seg[i].l==l&&seg[i].r==r){
        seg[i].val=v;
        seg[i].lazy=1;
        return;
    }
    if(seg[i].lazy){
        seg[2*i].val=seg[i].val;
        seg[2*i+1].val=seg[i].val;
        seg[2*i].lazy=seg[2*i+1].lazy=1;
        seg[i].lazy=0;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(r<=mid) update(2*i,l,r,v);
    else if(l>mid) update(2*i+1,l,r,v);
    else{
        update(2*i,l,mid,v);
        update(2*i+1,mid+1,r,v);
    }
}
int query(int i,int u){
    if(seg[i].l==u&&seg[i].r==u){
        return seg[i].val;
    }
    if(seg[i].lazy){
        seg[2*i].val=seg[i].val;
        seg[2*i+1].val=seg[i].val;
        seg[2*i].lazy=seg[2*i+1].lazy=1;
        seg[i].lazy=0;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(u<=mid) return query(2*i,u);
    else return query(2*i+1,u);
}
int main()
{
    int t;
    scanf("%d",&t);
    int icase=1;
    int n;
    while(t--){
        printf("Case #%d:\n",icase++);
        int u,v;
        memset(vis,0,sizeof(vis));
        init();
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            vis[u]=true;
            addedge(v,u);
        }
        //找到根节点
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                dfs(i);
                break;
            }
        }
        build(1,1,n);
        int m;
        scanf("%d",&m);
        char op[10];
        while(m--){
            scanf("%s",op);
            if(op[0]=='C'){
                scanf("%d",&u);
                printf("%d\n",query(1,start[u]));
            }
            else{
                scanf("%d%d",&u,&v);
                update(1,start[u],en[u],v);
            }
        }
    }
    return 0;
}

最大连续子区间问题

最大连续子区间对应的查询问题，为给定区间$[l,r]$内最大的连续子区间。。线段树中的节点维护该节点对应区间的最大连续子区间，左端最大连续子区间，右端最大连续子区间。根据左右孩子的最大连续子区间情况来更新当前节点的最大连续子区间情况。更新一般是区间合并或者区间拆分操作。

hdu 1540

初始状态所有的区间均连续，操作涉及到破坏和修复某个点两种，查询$x$所在最大连续子区间。

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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=50005;
struct Node{
    int l,r;
    int ll,rl,ml;
};
Node seg[maxn*3];
void build(int i,int l,int r){
    seg[i].l=l;
    seg[i].r=r;
    seg[i].ll=seg[i].rl=seg[i].ml=r-l+1;
    if(l==r) return;
    int mid=(seg[i].l+seg[i].r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
}
void update(int i,int k,int v){
    if(seg[i].l==seg[i].r){
        if(v==1) seg[i].ll=seg[i].rl=seg[i].ml=1;
        else seg[i].ll=seg[i].rl=seg[i].ml=0;
        return;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(k<=mid) update(2*i,k,v);
    else update(2*i+1,k,v);
    seg[i].ll=seg[2*i].ll;
    seg[i].rl=seg[2*i+1].rl;
    seg[i].ml=max(seg[2*i].ml,seg[2*i+1].ml);
    seg[i].ml=max(seg[i].ml,seg[2*i].rl+seg[2*i+1].ll);
    if(seg[2*i].ll==seg[2*i].r-seg[2*i].l+1) seg[i].ll+=seg[2*i+1].ll;
    if(seg[2*i+1].rl==seg[2*i+1].r-seg[2*i+1].l+1){
        seg[i].rl+=seg[2*i].rl;
    }
}
int que[maxn];
int top;
int query(int i,int t){
    if(seg[i].l==seg[i].r||seg[i].ml==0||seg[i].ml==seg[i].r-seg[i].l+1){
        return seg[i].ml;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(t<=mid){
        if(t>=seg[2*i].r-seg[2*i].rl+1){
            return seg[2*i].rl+seg[2*i+1].ll;
        }
        else return query(2*i,t);
    }
    else{
        if(t<=seg[2*i+1].l+seg[2*i+1].ll-1){
            return seg[2*i].rl+seg[2*i+1].ll;
        }
        else return query(2*i+1,t);
    }
}

int main()
{
    int n,m;
    char str[10];
    while(scanf("%d%d",&n,&m)==2){
        build(1,1,n);
        top=0;
        while(m--){
            scanf("%s",str);
            int x;
            if(str[0]=='D'){
                scanf("%d",&x);
                que[top++]=x;
                update(1,x,0);
            }
            else if(str[0]=='Q'){
                scanf("%d",&x);
                printf("%d\n",query(1,x));
            }
            else{
                if(x>0){
                    x=que[--top];
                    update(1,x,1);
                }
            }
        }
    }

    return 0;
}

POJ 3368

给定单调非减序列，查询区间$[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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100005;
struct Node{
    int l,r;
    int ll,rl,ml;
};
Node seg[maxn*3];
int a[maxn];
void build(int i,int l,int r){
    seg[i].l=l;
    seg[i].r=r;
    if(l==r){
        seg[i].ll=seg[i].rl=seg[i].ml=1;
        return;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
    int temp;
    if(a[seg[2*i].r]==a[seg[2*i+1].l]){
        temp=seg[2*i].rl+seg[2*i+1].ll;
    }
    else{
        temp=0;
    }
    seg[i].ml=max(max(seg[2*i].ml,seg[2*i+1].ml),temp);
    seg[i].ll=seg[2*i].ll;
    if(seg[2*i].ll==mid-l+1&&a[seg[2*i].r]==a[seg[2*i+1].l]){
        seg[i].ll+=seg[2*i+1].ll;
    }
    seg[i].rl=seg[2*i+1].rl;
    if(seg[2*i+1].rl==r-mid&&a[seg[2*i].r]==a[seg[2*i+1].l]){
        seg[i].rl+=seg[2*i].rl;
    }
}
int query(int i,int l,int r){
    if(seg[i].l==l&&seg[i].r==r){
        return seg[i].ml;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(r<=mid) return query(2*i,l,r);
    else if(l>mid) return query(2*i+1,l,r);
    else{
        int a1=query(2*i,l,mid);
        int a2=query(2*i+1,mid+1,r);
        int a3=0;
        if(a[seg[2*i].r]==a[seg[2*i+1].l]){
            a3=min(seg[2*i].rl,mid-l+1)+min(seg[2*i+1].ll,r-mid);
        }
        return max(max(a1,a2),a3);
    }
}

int main()
{
    int n;
    while(scanf("%d",&n)==1){
        if(n==0) break;
        int q;
        scanf("%d",&q);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        build(1,1,n);
        int x,y;
        for(int i=0;i<q;i++){
            scanf("%d%d",&x,&y);
            printf("%d\n",query(1,x,y));
        }
    }
    return 0;
}

区间更新和区间查询

hdu 1698

区间更新，查询所有区间的区间和

lazy作为延迟标记，tag标记区间更新的值

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100005;
int l[maxn],r[maxn];
struct Node{
    int l,r;
    int lazy,tag;
    int sum;
};
Node seg[maxn*3];
void build(int i,int l,int r){
    seg[i].l=l;
    seg[i].r=r;
    seg[i].lazy=0;
    seg[i].tag=0;
    if(l==r){
        seg[i].sum=1;
        return;
    }
    int mid=(l+r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
    seg[i].sum=seg[2*i].sum+seg[2*i+1].sum;
}
void update(int i,int l,int r,int v){
    if(seg[i].l==l&&seg[i].r==r){
        seg[i].lazy=1;
        seg[i].tag=v;
        seg[i].sum=(r-l+1)*v;
        return;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(seg[i].lazy){
        seg[i].lazy=0;
        update(2*i,seg[i].l,mid,seg[i].tag);
        update(2*i+1,mid+1,seg[i].r,seg[i].tag);
        seg[i].tag=0;
    }
    if(r<=mid) update(2*i,l,r,v);
    else if(l>mid) update(2*i+1,l,r,v);
    else{
        update(2*i,l,mid,v);
        update(2*i+1,mid+1,r,v);
    }
    seg[i].sum=seg[2*i].sum+seg[2*i+1].sum;
}
int main()
{
    int t;
    int n,m;
    scanf("%d",&t);
    int cnt=1;
    while(t--){
        scanf("%d%d",&n,&m);
        build(1,1,n);
        while(m--){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            update(1,x,y,z);
        }
        printf("Case %d: The total value of the hook is %d.\n",cnt++,seg[1].sum);
    }
	return 0;
}

POJ 3468

区间更新，区间查询，查询区间和

对于每个节点维护两个值

  1. 给这个节点对应区间内的所有元素共同加上的值
  2. 在这个区间内除去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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
int n,q;
char str[5];
const int maxn=1e5+5;
int a;
int l,r,x;
const int N=(1<<18)-1;
ll data[N],datb[N];
void add(int a, int b, int x, int k, int l, int r)
{
    if (a <= l && r <= b) {
        data[k] += x;
    }
    else if (l < b && a < r) {
        datb[k] += (min(b,r)-max(a,l))* x;
        add(a, b, x, k * 2 + 1, l, (l + r) / 2);
        add(a, b, x, k * 2 + 2, (l + r) / 2, r);
    }
}
ll sum(int a, int b, int k, int l, int r)
{
    if (b <= l || r <= a) {
        return 0;
    }
    else if(a <= l && r <= b){
        return data[k] * (r - l) + datb[k];
    }
    else {
        ll res = (min(b,r)-max(a,l)) * data[k];
        res += sum(a, b, k * 2 + 1, l, (l + r) / 2);
        res += sum(a, b, k * 2 + 2, (l + r) / 2, r);
        return res;
    }
}

int main(){
    scanf("%d%d",&n,&q);
    memset(data,0,sizeof(data));
    memset(datb,0,sizeof(datb));
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        add(i,i+1,a,0,0,n);
    }
    while(q--){
        scanf("%s",str);
        if(str[0]=='C'){
            scanf("%d%d%d",&l,&r,&x);
            add(l-1,r,x,0,0,n);
        }
        else{
            scanf("%d%d",&l,&r);
            printf("%lld\n",sum(l-1,r,0,0,n));
        }
    }
    return 0;
}

区间染色问题

ZOJ 1610

每次测试结束后输出所有可以显示的颜色和该颜色的段数。

注意这里的染色是对区间操作而不是对区间端点操作，通常情况下线段树操作是对区间端点操作。

线段树维护结构体信息

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=8005;
struct Node{
    int l,r;
    int val;
};
Node seg[maxn*3];
int ans[maxn],num[maxn];
void build(int i,int l,int r){
    seg[i].l=l;
    seg[i].r=r;
    seg[i].val=-1;
    if(l==r) return;
    int mid=(l+r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
}
void update(int i,int l,int r,int x){
    if(seg[i].l>=l&&seg[i].r<=r){
        seg[i].val=x;
        return;
    }
    if(seg[i].val!=-1){
        seg[2*i].val=seg[2*i+1].val=seg[i].val;
        seg[i].val=-1;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(l<=mid) update(2*i,l,r,x);
    if(r>mid) update(2*i+1,l,r,x);
}

void query(int i,int l, int r)
{
	if(seg[i].val!=-1)
	{
		for(int j = l; j <= r; j++)
			ans[j] = seg[i].val;
		return;
	}
	if(l==r) return;
    int mid =(l + r)/2;
    query(2*i,l,mid);
    query(2*i+1,mid+1,r);
}

int main()
{
    int n;
    while(scanf("%d",&n)==1){
        build(1,1,8000);
        memset(num, 0, sizeof(num));
        memset(ans, -1, sizeof(ans));
        for(int i=0;i<n;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            update(1,a+1,b,c);
        }
        query(1,1,8000);
        if(ans[0] != -1)
            num[ans[0]] ++;
        for(int i = 1; i <= 8000; i++)
            if(ans[i] != -1 && ans[i] != ans[i - 1])
                num[ans[i]] ++;
        for(int i = 0; i <= 8000; i++)
            if(num[i])
                printf("%d %d\n", i, num[i]);
        printf("\n");
    }
}

线段树维护数组信息

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=8005;
int val[maxn*3],num[maxn];
int ans[maxn];
void update(int i,int L,int R,int l,int r,int x){
    if(L<=l&&r<=R){
        val[i]=x;
        return;
    }
    int mid=(l+r)/2;
    if(val[i]!=-1){
        val[2*i]=val[2*i+1]=val[i];
        val[i]=-1;
    }
    if(L<=mid){
        update(2*i,L,R,l,mid,x);
    }
    if(R>mid){
        update(2*i+1,L,R,mid+1,r,x);
    }
}

void query(int i,int l,int r)
{
	if(val[i]!=-1)
	{
		for(int j=l;j<=r;j++)
			ans[j]=val[i];
		return;
	}
	if(l<r&& val[i]==-1)
	{
		int mid=(l+r)/2;
		query(2*i,l,mid);
		query(2*i+1,mid+1,r);
	}
}

int main()
{
    int n;
    while(scanf("%d",&n)==1){
        memset(num, 0, sizeof(num));
        memset(ans, -1, sizeof(ans));
        memset(val, -1, sizeof(val));
        for(int i=0;i<n;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            update(1,a+1,b,1,8000,c);
        }
        query(1,1,8000);
        if(ans[0] != -1)
            num[ans[0]] ++;
        for(int i = 1; i <= 8000; i++)
            if(ans[i] != -1 && ans[i] != ans[i - 1])
                num[ans[i]] ++;
        for(int i = 0; i <= 8000; i++)
            if(num[i])
                printf("%d %d\n", i, num[i]);
        printf("\n");
    }
}

POJ 2528

区间染色问题，求最后区间存在多少种不同的颜色

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn=100005;
int l[maxn],r[maxn];
vector<int> num;
struct Node{
    int l,r;
    int val;
};
Node seg[maxn*2];
int ans[maxn];
void build(int i,int l,int r){
    seg[i].l=l;
    seg[i].r=r;
    seg[i].val=0;
    if(l==r) return;
    int mid=(l+r)/2;
    build(2*i,l,mid);
    build(2*i+1,mid+1,r);
}
void update(int i,int l,int r,int x){
    if(seg[i].l>=l&&seg[i].r<=r){
        seg[i].val=x;
        return;
    }
    if(seg[i].val!=0){
        seg[2*i].val=seg[2*i+1].val=seg[i].val;
        seg[i].val=0;
    }
    int mid=(seg[i].l+seg[i].r)/2;
    if(l<=mid) update(2*i,l,r,x);
    if(r>mid) update(2*i+1,l,r,x);
}
void query(int i,int l,int r){
    if(seg[i].val){
        ans[seg[i].val]=1;
        return;
    }
    if(seg[i].l==seg[i].r) return;
    int mid=(seg[i].l+seg[i].r)/2;
    if(seg[i].val!=0){
        seg[2*i].val=seg[2*i+1].val=seg[i].val;
        seg[i].val=0;
    }
    query(2*i,l,r);
    query(2*i+1,l,r);
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        num.clear();
        for(int i=1;i<=n;i++){
            scanf("%d%d",&l[i],&r[i]);
            num.push_back(l[i]);
            num.push_back(r[i]);
        }
        sort(num.begin(),num.end());
        num.erase(unique(num.begin(),num.end()),num.end());
        int m=num.size();
        for(int i=0;i<m-1;i++){
            if(num[i+1]-num[i]>1){
                num.push_back(num[i+1]-1);
            }
        }
        sort(num.begin(),num.end());
        build(1,0,num.size()-1);
        int x,y;
        for(int i=1;i<=n;i++){
            x=lower_bound(num.begin(),num.end(),l[i])-num.begin();
            y=lower_bound(num.begin(),num.end(),r[i])-num.begin();
            update(1,x,y,i);
        }
        int res=0;
        memset(ans,0,sizeof(ans));
        query(1,0,num.size()-1);
        for(int i=1;i<=n;i++){
            if(ans[i]){
                res++;
            }
        }
        printf("%d\n",res);
    }

	return 0;
}

最大连续子区间问题

hdu 4553

比较复杂的线段树问题，对于女神和屌丝操作优先级不同，所以维护两个线段树。

对屌丝的更新操作无法覆盖女神的信息，而女神的更新信息可以覆盖屌丝的信息，更新操作则将女神和屌丝区间均清空。

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100005;
struct Node
{
    int l,r;
    int ll,rl,ml;
    int ll1,rl1,ml1;
};
Node seg[maxn*3];
void build(int i,int l,int r)
{
    seg[i].l=l;
    seg[i].r=r;
    seg[i].ml=seg[i].ll=seg[i].rl=r-l+1;
    seg[i].ml1=seg[i].ll1=seg[i].rl1=r-l+1;
    if(l==r)return;
    int mid=(l+r)/2;
    build(i<<1,l,mid);
    build((i<<1)|1,mid+1,r);
}
int query(int i,int x)
{
    if(seg[i].ml<x)return 0;
    if(seg[i].ll>=x)return seg[i].l;
    if(seg[i<<1].ml>=x)return query(i<<1,x);
    if(seg[i<<1].rl+seg[(i<<1)|1].ll>=x)return seg[i<<1].r-seg[i<<1].rl+1;
    return query((i<<1)|1,x);
}
int query1(int i,int x)
{
    if(seg[i].ml1<x)return 0;
    if(seg[i].ll1>=x)return seg[i].l;
    if(seg[i<<1].ml1>=x)return query1(i<<1,x);
    if(seg[i<<1].rl1+seg[(i<<1)|1].ll1>=x)return seg[i<<1].r-seg[i<<1].rl1+1;
    return query1((i<<1)|1,x);
}
void pushup(int x)
{
    if(seg[x].l==seg[x].r)return;
    int lson=2*x;
    int rson=2*x+1;
    seg[x].ll=seg[lson].ll;
    if(seg[lson].ll==seg[lson].r-seg[lson].l+1)seg[x].ll+=seg[rson].ll;
    seg[x].rl=seg[rson].rl;
    if(seg[rson].rl==seg[rson].r-seg[rson].l+1)seg[x].rl+=seg[lson].rl;
    seg[x].ml=max(seg[lson].ml,seg[rson].ml);
    seg[x].ml=max(seg[x].ml,max(seg[x].ll,seg[x].rl));
    seg[x].ml=max(seg[x].ml,seg[lson].rl+seg[rson].ll);

    seg[x].ll1=seg[lson].ll1;
    if(seg[lson].ll1==seg[lson].r-seg[lson].l+1)seg[x].ll1+=seg[rson].ll1;
    seg[x].rl1=seg[rson].rl1;
    if(seg[rson].rl1==seg[rson].r-seg[rson].l+1)seg[x].rl1+=seg[lson].rl1;
    seg[x].ml1=max(seg[lson].ml1,seg[rson].ml1);
    seg[x].ml1=max(seg[x].ml1,max(seg[x].ll1,seg[x].rl1));
    seg[x].ml1=max(seg[x].ml1,seg[lson].rl1+seg[rson].ll1);
}

void pushdown(int i)
{
    if(seg[i].l==seg[i].r)return;
    if(seg[i].ml==0)
    {
        seg[2*i].ml=seg[2*i].ll=seg[2*i].rl=0;
        seg[2*i+1].ml=seg[2*i+1].ll=seg[2*i+1].rl=0;
    }
    if(seg[i].ml==seg[i].r-seg[i].l+1)
    {
        seg[2*i].ml=seg[2*i].ll=seg[2*i].rl=seg[2*i].r-seg[2*i].l+1;
        seg[2*i+1].ml=seg[2*i+1].ll=seg[2*i+1].rl=seg[2*i+1].r-seg[2*i+1].l+1;
    }


    if(seg[i].ml1==0)
    {
        seg[2*i].ml1=seg[2*i].ll1=seg[2*i].rl1=0;
        seg[2*i+1].ml1=seg[2*i+1].ll1=seg[2*i+1].rl1=0;
    }
    if(seg[i].ml1==seg[i].r-seg[i].l+1)
    {
        seg[2*i].ml1=seg[2*i].ll1=seg[2*i].rl1=seg[2*i].r-seg[2*i].l+1;
        seg[2*i+1].ml1=seg[2*i+1].ll1=seg[2*i+1].rl1=seg[2*i+1].r-seg[2*i+1].l+1;
    }

}
void update(int i,int l,int r)
{
    if(seg[i].l==l && seg[i].r==r)
    {
        seg[i].ml=seg[i].ll=seg[i].rl=seg[i].r-seg[i].l+1;
        seg[i].ml1=seg[i].ll1=seg[i].rl1=seg[i].r-seg[i].l+1;
        return;
    }
    pushdown(i);
    int mid=(seg[i].l+seg[i].r)/2;
    if(r<=mid)update(i<<1,l,r);
    else if(l>mid) update((i<<1)|1,l,r);
    else
    {
        update(i<<1,l,mid);
        update((i<<1)|1,mid+1,r);
    }
    pushup(i);
}
void update1(int i,int l,int r)
{
    if(seg[i].l==l && seg[i].r==r)
    {
        seg[i].ml=seg[i].ll=seg[i].rl=0;
        return;
    }
    pushdown(i);
    int mid=(seg[i].l+seg[i].r)/2;
    if(r<=mid)update1(i<<1,l,r);
    else if(l>mid) update1((i<<1)|1,l,r);
    else
    {
        update1(i<<1,l,mid);
        update1((i<<1)|1,mid+1,r);
    }
    pushup(i);
}
void update2(int i,int l,int r)
{
    if(seg[i].l==l && seg[i].r==r)
    {
        seg[i].ml=seg[i].ll=seg[i].rl=0;
        seg[i].ml1=seg[i].ll1=seg[i].rl1=0;
        return;
    }
    pushdown(i);
    int mid=(seg[i].l+seg[i].r)/2;
    if(r<=mid)update2(i<<1,l,r);
    else if(l>mid) update2((i<<1)|1,l,r);
    else
    {
        update2(i<<1,l,mid);
        update2((i<<1)|1,mid+1,r);
    }
    pushup(i);
}

int main()
{
    int t;
    int cnt=1;
    scanf("%d",&t);
    while(t--){
        int n,m;
        printf("Case %d:\n",cnt++);
        scanf("%d%d",&n,&m);
        build(1,1,n);
        char op[10];
        int x;
        for(int i=0;i<m;i++){
            scanf("%s",op);
            int l,r;
            if(op[0]=='D'){
                scanf("%d",&x);
                int tmp=query(1,x);
                if(tmp==0) printf("fly with yourself\n");
                else{
                    update1(1,tmp,tmp+x-1);
                    printf("%d,let's fly\n",tmp);
                }
            }
            else if(op[0]=='N'){
                scanf("%d",&x);
                int tmp=query(1,x);
                if(tmp!=0){
                    update2(1,tmp,tmp+x-1);
                    printf("%d,don't put my gezi\n",tmp);
                    continue;
                }
                tmp=query1(1,x);
                if(tmp!=0){
                    update2(1,tmp,tmp+x-1);
                    printf("%d,don't put my gezi\n",tmp);
                    continue;
                }
                printf("wait for me\n");
            }
            else{
                scanf("%d%d",&l,&r);
                printf("I am the hope of chinese chengxuyuan!!\n");
                update(1,l,r);
            }
        }
    }
    return 0;
}