详解请点击此处 http://blog.csdn.net/zearot/article/details/48299459
递归版
(我的)线段树要点
- 开数组的时候开到4*n即可。
- 若只涉及线段树的点修改或要进行单点查询,则要记录每个单点区间的编号(用fat数组),并在修改此单点区间后向上更新。
- 若涉及到线段树的区间修改,且不涉及单点查询,则不需要记录单点区间编号,并且更新过程利用lazy标记从上往下,直至区间刚好吻合。
- 区间合并时注意细节
基本函数
自定义:
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
int node[maxn<<2], lazy[maxn<<2];
build(int l, int r, int now); (建树函数)
函数调用: build(1,n,1);
void build(int l, int r, int now) {
if(l==r) {
a[l]=node[now]=read();
return;
}
int m=(l+r)/2;
build(ls);
build(rs);
node[now]=node[now<<1]+node[now<<1|1];
}
update(int l, int r, int now); (单点修改)
以求和为例
函数调用:update(pos,d,1,n,1);
void update(int pos, int d, int l, int r, int now) {
if(l==r) {
node[now]+=d;
return;
}
int m=(l+r)/2;
if(pos<=m) update(pos,d,ls);
if(pos>m) update(pos,d,rs);
node[now]=node[now<<1]+node[now<<1|1];
}
push_down(int ln, int rn, int now); (下推标记)
函数调用:push_down(m-l+1,r-m,now);
void push_down(int ln, int rn, int now) {
if(lazy[now]) {
int p=lazy[now];
lazy[now]=0;
lazy[now<<1]+=p;
lazy[now<<1|1]+=p;
node[now<<1]+=p*ln;
node[now<<1|1]+=p*rn;
}
}
update(int x, int y, int d, int l, int r, int now); (区间修改)
以求和为例
[x,y]为修改区间,[l,r]为当前线段树区间
函数调用:update(x,y,d,1,n,1);
void update(int x, int y, int d, int l, int r, int now) {
if(x<=l&&r<=y) {
node[now]+=(r-l+1)*d;
lazy[now]+=d;
return;
}
int m=(l+r)/2;
push_down(m-l+1,r-m,now);
if(x<=m) update(x,y,d,ls);
if(y>m) update(x,y,d,rs);
node[now]=node[now<<1]+node[now<<1|1];
}
query(int x, int y, int l, int r, int now);
以区间求和为例
函数调用:query(x,y,1,n,1);
int query(int x, int y, int l, int r, int now) {
if(x<=l&&r<=y) {
return node[now];
}
int m=(l+r)/2;
push_down(m-l+1,r-m,now);
int ans=0;
if(x<=m) ans+=query(x,y,ls);
if(y>m) ans+=query(x,y,rs);
return ans;
}
模板题分析
以下例题早期采用结构体版本的线段树,暂未更改为上述简易模板
HDOJ 1166 地兵布阵(单点更新+区间求和)
Problem Description
C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.
Input
第一行一个整数T,表示有T组数据。
每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
接下来每行有一条命令,命令有4种形式:
(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
(4)End 表示结束,这条命令在每组数据最后出现;
每组数据最多有40000条命令
Output
对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
Sample Input
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
Sample Output
Case 1:
6
33
59
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
const int MAX=50005;
struct Node{
int l, r, v;
int mid() {
return (l+r)>>1;
}
}node[MAX<<2];
int fat[MAX<<1];
void build(int l, int r, int now) {
node[now].l=l;
node[now].r=r;
node[now].v=0;
if(l==r) {
node[now].v=0;
fat[l]=now;
return;
}
int m=node[now].mid();
build(l,m,now<<1);
build(m+1,r,now<<1|1);
}
void updata(int now, int d) {
node[now].v+=d;
if(now==1) return;
updata(now>>1, d);
}
int sum(int l, int r, int now) {
if(node[now].l==l&&node[now].r==r) return node[now].v;
int m=node[now].mid();
if(r<=m) return sum(l,r,now<<1);
if(l>m) return sum(l,r,now<<1|1);
return sum(l,m,now<<1)+sum(m+1,r,now<<1|1);
}
int main() {
ios::sync_with_stdio(false);
int T, t;
scanf("%d", &T);
t=T;
while(T--) {
printf("Case %d:\n", t-T);
int N;
scanf("%d", &N);
build(1,N,1);
for(int i=1; i<=N; ++i) {
int d;
scanf("%d", &d);
updata(fat[i], d);
}
char s[20];
while(scanf("%s", s)) {
if(s[0]=='E') break;
if(s[0]=='Q') {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", sum(x,y,1));
}
else {
int x, y;
scanf("%d%d", &x, &y);
if(s[0]=='S') y=-y;
updata(fat[x], y);
}
}
}
return 0;
}
HDOJ 3308 LCIS(单点更新+区间合并)
Problem Description
Given n integers.
You have two operations:
U A B: replace the Ath number by B. (index counting from 0)
Q A B: output the length of the longest consecutive increasing subsequence (LCIS) in [a, b].
Input
T in the first line, indicating the case number.
Each case starts with two integers n , m(0<n,m<=105).
The next line has n integers(0<=val<=105).
The next m lines each has an operation:
U A B(0<=A,n , 0<=B=105)
OR
Q A B(0<=A<=B< n).
Output
For each Q, output the answer.
Sample Input
1
10 10
7 7 3 3 5 9 9 8 1 8
Q 6 6
U 3 4
Q 0 1
Q 0 5
Q 4 7
Q 3 5
Q 0 2
Q 4 6
U 6 10
Q 0 9
Sample Output
1
1
4
2
3
1
2
5
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
const int MAXN=100010;
struct Node{
int l, r;
int len;
int m() {
return (l+r)/2;
}
}node[MAXN<<2];
int d[MAXN], fat[MAXN];
int n, m;
void build(int l, int r, int now) {
node[now].l=l;
node[now].r=r;
node[now].len=1;
if(l==r) {
fat[l]=now;
return;
}
int m=node[now].m();
build(l,m,now<<1);
build(m+1,r,now<<1|1);
}
void update(int now) {
if(now==1) return;
int p=now>>1;
int l=node[p].l;
int r=node[p].r;
int i=1, j=1, m=node[p].m(); //区间合并一定要非常小心
for( ; m-i>=l&&d[m-i]<d[m-i+1]; ++i);
for( ; m+j<=r&&d[m+j]>d[m+j-1]; ++j);
node[p].len=max(i+j-1,max(node[p<<1].len,node[p<<1|1].len));
update(p);
}
int qy(int l, int r, int now) {
if(l==node[now].l&&r==node[now].r) return node[now].len;
int m=node[now].m();
if(r<=m) return qy(l,r,now<<1);
if(l>m) return qy(l,r,now<<1|1);
int i=1, j=1;
for( ; m-i>=l&&d[m-i]<d[m-i+1]; ++i);
for( ; m+j<=r&&d[m+j]>d[m+j-1]; ++j);
return max(i+j-1,max(qy(l,m,now<<1),qy(m+1,r,now<<1|1)));
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
build(1,n,1);
for(int i=1; i<=n; ++i) {
scanf("%d", &d[i]);
update(fat[i]);
}
while(m--) {
char c;
int a, b;
cin>>c>>a>>b;
if(c=='U') {
a++;
d[a]=b;
update(fat[a]);
}
else {
a++, b++;
printf("%d\n", qy(a, b, 1));
}
}
}
return 0;
}
HDOJ 4267 A Simple Problem with Integers (区间更新+单点查询+状态压缩)
Problem Description
Let A1, A2, … , AN be N elements. You need to deal with two kinds of operations. One type of operation is to add a given number to a few numbers in a given interval. The other is to query the value of some element.
Input
There are a lot of test cases.
The first line contains an integer N. (1 <= N <= 50000)
The second line contains N numbers which are the initial values of A1, A2, … , AN. (-10,000,000 <= the initial value of Ai <= 10,000,000)
The third line contains an integer Q. (1 <= Q <= 50000)
Each of the following Q lines represents an operation.
“1 a b k c” means adding c to each of Ai which satisfies a <= i <= b and (i - a) % k == 0. (1 <= a <= b <= N, 1 <= k <= 10, -1,000 <= c <= 1,000)
“2 a” means querying the value of Aa. (1 <= a <= N)
Output
For each test case, output several lines to answer all query operations.
Sample Input
4
1 1 1 1
14
2 1
2 2
2 3
2 4
1 2 3 1 2
2 1
2 2
2 3
2 4
1 1 4 2 1
2 1
2 2
2 3
2 4
Sample Output
1
1
1
1
1
3
3
1
2
3
4
1
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<cctype>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
const int MAXN=50010;
struct Node{
bool f;
int data;
int l, r;
int add[55];
int m() {
return (l+r)/2;
}
}node[MAXN<<2];
int N;
void build(int l, int r, int now) {
node[now].f=0;
node[now].l=l;
node[now].r=r;
memset(node[now].add,0,sizeof(node[now].add));
if(l==r) {
scanf("%d", &node[now].data);
return;
}
build(l,node[now].m(),now<<1);
build(node[now].m()+1,r,now<<1|1);
}
void updata(int l, int r, int now, int c, int p) {
if(l==node[now].l&&r==node[now].r) {
node[now].add[p]+=c;
node[now].f=1;
return;
}
int m=node[now].m();
if(r<=m) updata(l,r,now<<1,c,p);
else if(l>m) updata(l,r,now<<1|1,c,p);
else {
updata(l,m,now<<1,c,p);
updata(m+1,r,now<<1|1,c,p);
}
}
void pd(int now) {
for(int i=0; i<55; ++i) {
node[now<<1].add[i]+=node[now].add[i];
node[now<<1|1].add[i]+=node[now].add[i];
node[now].add[i]=0;
}
node[now].f=0;
node[now<<1].f=1;
node[now<<1|1].f=1;
}
int ans;
void qy(int x, int now) {
if(node[now].l==node[now].r) {
for(int i=1; i<=10; ++i) {
node[now].data+=node[now].add[i*(i-1)/2+x%i];
node[now].add[i*(i-1)/2+x%i]=0;
}
ans=node[now].data;
return;
}
if(node[now].f) pd(now);
if(x<=node[now].m()) qy(x,now<<1);
else qy(x,now<<1|1);
}
int main() {
while(scanf("%d", &N)!=EOF) {
build(1,N,1);
int Q;
scanf("%d", &Q);
while(Q--) {
int f, a, b, c, k;
scanf("%d", &f);
if(f==1) {
scanf("%d%d%d%d", &a, &b, &k, &c);
updata(a,b,1,c,k*(k-1)/2+a%k);
}
else {
scanf("%d", &a);
qy(a,1);
printf("%d\n", ans);
}
}
}
}
非递归版(张昆玮—zkw线段树)
大致思想,利用左右两个端点将查询区间包住,然后像两条链子一样向上更新。
弄清几个关键词:
- N(>=n+2)
- 原数组下标+N=存储下标
- s ^ t ^ 1 : 在s和t的父亲相同时值为0
具体细节请查看文章开头的链接。
函数(以求和为例)
定义
#define maxn 100007
int A[maxn],n,N;//原数组,n为原数组元素个数 ,N为扩充元素个数
int Sum[maxn<<2];//区间和
int Add[maxn<<2];//懒惰标记
建树
void Build(int n){
//计算N的值
N=1;while(N < n+2) N <<= 1;
//更新叶节点
for(int i=1;i<=n;++i) Sum[N+i]=A[i];//原数组下标+N=存储下标
//更新非叶节点
for(int i=N-1;i>0;--i){
//更新所有非叶节点的统计信息
Sum[i]=Sum[i<<1]+Sum[i<<1|1];
//清空所有非叶节点的Add标记
Add[i]=0;
}
}
点修改
void Update(int L,int C){
for(int s=N+L;s;s>>=1){
Sum[s]+=C;
}
}
点修改下的区间查询
求A[L…R]的和(点修改没有使用Add所以不需要考虑)
代码非常简洁,也不难理解,
s和t分别代表之前的论述中的左右蓝色节点,其余的代码根据之前的论述应该很容易看懂了。
st1 在s和t的父亲相同时值为0,终止循环。
两个if是判断s和t分别是左子节点还是右子节点,根据需要来计算Sum
int Query(int L,int R){
int ANS=0;
for(int s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1){
if(~s&1) ANS+=Sum[s^1];
if( t&1) ANS+=Sum[t^1];
}
return ANS;
}
区间修改
void Update(int L,int R,int C){
int s,t,Ln=0,Rn=0,x=1;
//Ln: s一路走来已经包含了几个数
//Rn: t一路走来已经包含了几个数
//x: 本层每个节点包含几个数
for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){
//更新Sum
Sum[s]+=C*Ln;
Sum[t]+=C*Rn;
//处理Add
if(~s&1) Add[s^1]+=C,Sum[s^1]+=C*x,Ln+=x;
if( t&1) Add[t^1]+=C,Sum[t^1]+=C*x,Rn+=x;
}
//更新上层Sum
for(;s;s>>=1,t>>=1){
Sum[s]+=C*Ln;
Sum[t]+=C*Rn;
}
}
区间修改下的区间查询
int Query(int L,int R){
int s,t,Ln=0,Rn=0,x=1;
int ANS=0;
for(s=N+L-1,t=N+R+1;s^t^1;s>>=1,t>>=1,x<<=1){
//根据标记更新
if(Add[s]) ANS+=Add[s]*Ln;
if(Add[t]) ANS+=Add[t]*Rn;
//常规求和
if(~s&1) ANS+=Sum[s^1],Ln+=x;
if( t&1) ANS+=Sum[t^1],Rn+=x;
}
//处理上层标记
for(;s;s>>=1,t>>=1){
ANS+=Add[s]*Ln;
ANS+=Add[t]*Rn;
}
return ANS;
}