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;
}

参考资料:http://blog.csdn.net/zearot/article/details/48299459

Last modification:October 14th, 2016 at 08:43 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏