1. 简述
线段树(英语:Segment tree)是一种二叉树形数据结构,用以储存区间或线段,并且允许快速查询结构内包含某一点的所有区间。
一个包含n个区间的线段树,空间复杂度为O(nlogN),查询的时间复杂度则为O(logN+k),其中k是符合条件的区间数量。
此数据结构亦可推广到高维度。
——维基百科
二叉树在OI竞赛中应用很广泛,主要用于区间查找中,还可以用于按时分治,甚至可用拓展到高维用来解决更加复杂的问题(但由于其空间复杂度和维护难度大不予考虑)。与树状数组相比,其编写难度要大上不少,但其强大的功能也是树状数组所不能及的。由于其时间复杂度为O(logN),会要比很多O(N^2)的暴力算法好上不少,同时通过lazytag的思想对其进行优化,可以大大提高查找的效率。
2.基本操作
零,定义
#define maxn 100007 //定义元素总个数
int sum[maxn<<2],add[maxn<<2];
//左移一位,开四倍maxn的大小数组分别用于求和于放置lazy标记
int a[maxn],n;
//存放原数组下标
可见线段树的空间复杂度十分高,线段树需要的数组元素个数是:2^(logN+1),一般都开4倍空间,比如: int a[n<<2]。虽然代价十分大,但是对于拿空间换时间的竞赛来说却是可行的。
一,建立
void pushup(int rt) {
//用于求左右两棵子树的和
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
//这里用到了一个小技巧,左移一位后末尾必为0,这时候与一个1相当于加1,比直接+1要快一点。
}
void build(int l,int r,int rt) {
//l,r表示当前节点区间,rt表示当前节点编号
if(r == l) {
sum[rt] = a[l];
return;
//如果达到根节点,则将根节点赋值为a中所对应值并且回溯
}
int m = (l+r)>>1;
build(l,m,rt<<1);
build(m,r,rt<<1|1);
左右递归
pushup(rt);
}
二,点修改
对a[p] += data
void update(int p,int data,int l,int r,int rt) {
if(l == r) {
//到达叶节点就修改,并回溯更新父节点
sum[rt] += c;
return;
}
int m = (l+r)>>1;
if(p <<= m) update(p,data,l,m,rt<<1);
else uptate(p,data,m,r,rt<<1|1);
//判断移动方向,如果p<<=m则向左树移动,反之则向右树移动
pushup(rt);
//更新父亲节点
}
三,区间修改
对a[l,r]+=data;
void pushdown(int rt,int ln,int rn){
//ln,rn为左子树,右子树的数字数量。
if(add[rt]){
//下推标记,如有则向下拓展
add[rt<<1] += add[rt];
add[rt<<1|1] += add[rt];
//修改子节点的Sum使之与对应的Add相对应
sum[rt<<1] += add[rt]*ln;
sum[rt<<1|1] += add[rt]*rn;
//清除本节点标记,相当于本来就该计算改点的值但是却放到现在才计算
add[rt] = 0;
}
}
void update(int dl,int dr,int data,int l,int r,int rt) {
if(dl <<= l && r <<= dr){//如果本区间完全在操作区间[L,R]以内
sum[rt] += data*(r-l+1);//更新数字和,向上保持正确
add[rt] += data;//增加lazy标记,表示本区间的sum正确,子区间的sum仍需要根据add的值来调整
return;
}
int m = (l+r)>>1;
pushdown(rt,m-l+1,r-m);//下推标记
//这里判断左右子树跟[L,R]有无交集,有交集才递归
if(dl <<=m) update(dl,dr,data,l,m,rt<<1);
if(dr > m) update(dl,dr,data,m+1,r,rt<<1|1);
pushup(rt);//更新本节点信息
}
四,区间查询
int query(int dl,int dr,int l,int r,int rt){
//dl,dr表示操作区间,l,r表示当前节点区间,rt表示当前节点编号
if(dl <<= l && r <<= dr){
//在区间内,直接返回
return sum[rt];
}
int m=(l+r)>>1;
//下推标记,否则Sum可能不正确
pushdown(rt,m-l+1,r-m);
//累计答案
int ans = 0;
if(dl <= m)
ans += query(dl,dr,l,m,rt<<1);
if(dr > m)
ans += query(dl,dr,m+1,r,rt<<1|1);
return ans;
}
五,完整代码
#include <cstdio>;
using namespace std;
//将以上代码放置于此(没错,我连复制都懒得复制了)
int main() {
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
build(1,n,1);
//建树
update(目标点,值,1,n,1);
update(左端点,右端点,值,1,n,1);
int que = query(左端点,右端点,1,n,1);
printf("%d",que);
return 0;
}
One comment
http://blog.csdn.net/qq_18455665/article/details/50989113 zkw线段树