线段树模板

发布于 2017-12-03  491 次阅读


一种快速的区间查找算法


线段树和树状数组一样,都可以在$ n log_2 n $ 的时间复杂度下求出一个动态区间的最优值。
模板一
模板二

定义

线段树是一种树形结构(这不是废话吗),它的每个结点存储的是一条线段。它是一个能在$ O(logn) $ 的时间复杂度中进行区间修改和区间查询操作的数据结构,常用于多次查询动态区间的最优值(或和)。

实现步骤

建树

我们当然是用递归构造线段树啦(这不是废话吗+1)。
我们对于一个区间,如果它的长度不为1,我们就取mid,然后将其分为两个子区间$ [l,mid] $ 和 $ [mid + 1,r] $。如果长度为1,我们就将其作为叶子节点。

Lazy-tag

显而易见,如果我们单点修改,我们只需要一直递归向上修改即可,但要对区间进行修改是,我们如果采取多次单点修改的花时间复杂度会飙升到$ O(n log_2 n) $,还不如朴素(暴力)算法。。。
看这个小标题就知道,在这里教你一种偷懒的方式,不需要那么勤奋。所以,我们可以引入Lazy-tag机制。
我们在每一个结点多去维护一个tag变量。如果我们要对区间$ [a,b] $进行统一加c操作,我们可以只先修改当前$ [a,b] $区间的值,同时我们给这个区间打上一个tag,表示该区间被整体加上了tag,方便以后查询时修正。
另外要注意在查询或修改一个结点的时候要将tag进行下方,即pushDown操作(这不是废话,这很重要!)

区间查询

当然是选择递归查询啦(这不是废话吗+2)

样例代码

代码为线段树的指针写法。
本代码以求和为基础。
实际运用时请注意数据范围。

#include<iostream>
#include<cstdio>
#include<cstring>

struct SegmentTree{   //线段树结构体
    int left,right,sum,tag;
    SegmentTree *lc,*rc;

    SegmentTree(int left,int right,SegmentTree *lc,SegmentTree *rc) : left(left), right(right), sum(0), tag(0), lc(lc), rc(rc) {}
    //线段树构造函数

    static SegmentTree *build(int l,int r){  //建立一个线段树
        int mid = (l + r) >> 1;
        return l == r ? new SegmentTree(l, r, NULL, NULL) : new SegmentTree(l, r, build(l,mid), build(mid + 1, r));
    }

    void cover(int delta){  //修改
        sum += delta * (right - left + 1);
        tag += delta;
    }

    void pushDown() {  //tag下方操作
        if(tag){
            lc->cover(tag);
            rc->cover(tag);
            tag = 0;
        }
    }

    void modify(int l, int r, int delta){  //对某一区间整体增加值
        if(l > right || r < left) return;
        else if(l <= left && r >= right) cover(delta);
        else{
            pushDown();
            lc->modify(l, r, delta);
            rc->modify(l, r, delta);
            sum = lc->sum + rc->sum;
        }
    }

    int query(int l, int r){   //查询某区间的和
        if(l > right || r < left) return 0;
        else if(l <= left && r >= right) return sum;
        else return pushDown(), lc->query(l, r) + rc->query(l, r);
    }
};


int main(){
    SegmentTree *segt; // 声明一个线段树
    int n,q,d,x,y,z; //n表示区间长度,q表示询问次数
    scanf("%d%d",&n,&q);
    segt = SegmentTree::build(1,n); //建树
    for(int i = 1;i <= n;i++){   //初始化线段树
        scanf("%d",&x);
        segt->modify(i,i,x);   //赋值操作,记住
    }
    for(int i = 1;i <= q;i++){
        scanf("%d%d%d",&d,&x,&y); //表示在[x,y]区间进行d操作
        if(d == 1){  //对某区间集体加z时的操作
            scanf("%d",&z);
            segt->modify(x,y,z);
        }
        else{   查询区间时的操作
            printf("%d%c",segt->query(x,y),'\n');
        }
    }
    return 0;  //完美的结束
}

一个OIer。