[数据结构与算法]线段树模板

线段树作用是将一个数组的 区间操作 和 单点操作 时间复杂度都平均为O（logn），原理便是建立一个完全二叉树来存储mid左右两个区间的信息（sum,min,max）以下模板以sum为例子。

而对于区间修改的情况，可以使用懒惰标记的方法，如果当前区间是在所操作区间之内就将其懒惰标记加上要加的值，而如果遍历到当前区间时如果有懒惰标记就将其下传并对自己的清零，这个操作对于所有函数都适用，因为懒惰标记名副其实很懒，只有你碰他他才动，不理他他永远就不变。

模板如下（包含建立线段树，区间加值，区间求和，单点修改，还有区间修改其他操作也可以用懒惰标记来实现）

#include <bits/stdc++.h>
using namespace std;
void build(int test[],int tree[],int l,int r,int p)
{
    if(l==r)
    {
        tree[p]=test[l];
        return;
    }
    
    int mid=(l+r)/2;
    build(test,tree,l,mid,2*p+1);
    build(test,tree,mid+1,r,2*p+2);
    tree[p]=tree[2*p+1]+tree[2*p+2];
}//建立线段树

void update(int lazy[],int tree[],int l,int r,int p,int q,int a)
{
    if(r==l)
    {
        tree[p]=a;
        return;
    }
    int mid=(l+r)/2;
    if(lazy[p] && l!=r)
    {
        lazy[2*p+1]+=lazy[p];
        lazy[2*p+2]+=lazy[p];
        tree[2*p+1]+=lazy[p]*(mid-l+1);
        tree[2*p+2]+=lazy[p]*(r-mid);
        lazy[p]=0;
    }//这个操作除了建立线段树以外所有函数都可以用
    if(q<=mid) update(lazy,tree,l,mid,2*p+1,q,a);
    else update(lazy,tree,mid+1,r,2*p+2,q,a);
    tree[p]=tree[2*p+1]+tree[2*p+2];
}//更新单点

void query_update(int lazy[],int tree[],int l,int r,int p,int q,int gl,int gr)
{
    if(gl<=l && r<=gr)
    {
        lazy[p]+=q;
        tree[p]+=(r-l+1)*q;
        return;
    }
    //if(gl>r || gr<l) return;

    int mid=(l+r)/2;
    
    if(lazy[p] && l!=r)
    {
        lazy[2*p+1]+=lazy[p];
        lazy[2*p+2]+=lazy[p];
        tree[2*p+1]+=lazy[p]*(mid-l+1);
        tree[2*p+2]+=lazy[p]*(r-mid);
        lazy[p]=0;
    }
    
    if(gl<=mid) query_update(lazy,tree,l,mid,2*p+1,q,gl,gr);
    if(gr>mid) query_update(lazy,tree,mid+1,r,2*p+2,q,gl,gr);
    
    tree[p]=tree[2*p+1]+tree[2*p+2];
}//区间更新

int query(int lazy[],int tree[],int l,int r,int p,int gl,int gr)
{
    if(gr<l || gl>r) return 0;
    if(gl<=l && r<=gr)  return tree[p];
    else 
    {        
        int mid=(l+r)/2;
        if(lazy[p] && l!=r)
        {
        lazy[2*p+1]+=lazy[p];
        lazy[2*p+2]+=lazy[p];
        tree[2*p+1]+=lazy[p]*(mid-l+1);
        tree[2*p+2]+=lazy[p]*(r-mid);
        lazy[p]=0;
        }

        int sum=0;
        sum+=query(lazy,tree,l,mid,2*p+1,gl,gr);
        sum+=query(lazy,tree,mid+1,r,2*p+2,gl,gr);
        return sum;
    }
}//区间求和


int main()
{
    int test[10]={5,3,2,1,6,4,10,12,16,8};
    int tree[40];
    int lazy[40];
    memset(tree,0,sizeof(tree));
    memset(lazy,0,sizeof(lazy));
    build(test,tree,0,9,0);
    for(int i=0;i<31;i++)
    {
        printf("tree[%d] = %d\n",i,tree[i]);
    }
    cout<<endl;
    update(lazy,tree,0,9,0,3,11);
    for(int i=0;i<31;i++)
    {
        printf("tree[%d] = %d\n",i,tree[i]);
    }
    
    int ans=query(lazy,tree,0,9,0,0,9);
    
    cout<<ans<<endl;
    
    query_update(lazy,tree,0,9,0,2,1,5);
    
    ans=query(lazy,tree,0,9,0,2,6);
    
    cout<<ans<<endl;
    
    return 0;
}

寒假接近尾声，希望新的学期有新的进步！