线段树模板（洛谷P3372）

阅读量：6760 次

发布时间：2019-06-26

本文共 2758 字，大约阅读时间需要 9 分钟。

给定序列，支持区间加、求区间和。

==线段树==的基本思路（线段树模板嘛，不懂得看题解第一，dalao讲解超详细的）

#include
    
     using namespace std;#define ll long longint MAXN=1000001;unsigned ll n,m,a[MAXN],ans[MAXN<<2],lazytag[MAXN<<2];

开头还用解释吗qaq

inline ll 左儿子inline ll 右儿子void 输入void 传递void 建树void 当前处理懒标记void 传递懒标记 void 更新ll 求和//当然在数据较小的时候可以用int，看着顺眼

以上是各函数的框架，都是线段树的基本函数。

int main(){    输入    建树    while(m--)    {    输入操作选项    case 1:    {    输入xyk     更新    break;     }     case 2:    {        输入xy        输出和        break；     }    }    return 0;}

主函数的设计思路还是比较简单的，不过要注意输入输出的优化，cincout可能会TLE吧，~~虽然没试过2333~~

接下来是填好了的主函数！一定要自己打一遍再看哦~

==真的自己打了吗？？？==

int main(){    ll op,x,y,k;     shuru();    buildtree(1,1,n);    while(m--)    {        scanf("%lld",&op);        switch(a1)        case 1:        {            scanf("%lld%lld%lld",&x,&y,&k);            update(x,y,1,n,1,k);            break;         }         case 2:        {            scanf("%lld%lld",&x,&y);             printf("%lld\n",query(x,y,1,n,1));            break;                    }    return 0;}

这些函数都是啥？？？接着往下看吧owo

先看比较简单的找左右儿子

根据二叉树的性质

父亲节点fa的左右儿子

分别是 fa<<2 和 fa<<2|1

这是~~zhaungbi~~优秀的位运算

表示fa2 和 fa2+1

你可以先不用理解它是什么意思

记住它的含义就好了

void shuru(){    cin>>n>>m;    for(ll i=1;i<=n;i++)    scanf("%lld",&a[i]);}

简单可爱的输入

void pushup(ll x){    ans[x]=ans[leftchild(x)]+ans[rightchild(x)];}void buildtree(int x,int l,int r){    lazytag[x]=0;    if(l==r)    {        ans[x]=a[l];        return;    }    ll mid=(l+r)>>1;    build(leftchild(x),l,mid);    build(rightchild(x),mid+1,r);    pushup(p);}

二分的方法建树

如果是叶子节点，那么它的值就是自己

如果是父亲节点，就是它的儿子的和

初始化懒标记为0，表示暂时没有向下传递的数据

void lazy(ll x,ll l,ll r,ll k){    lazytag[x]=lazytag[x]+k;    ans[x]=ans[x]+k*(r-l+1);    lazytag[x]=0;}void pushdown(ll x,ll l,ll r){    ll mid=(l+r)>>1;    lazy(leftchild(x),l,mid,lazytag[x]);    lazy(rightchild(x),mid+1,r,lazytag[x]);}void update(ll L,ll R,ll l,ll r,ll x,ll k){    //[L,R]为要求查询区间,查询过程中不能变     if(L<=l && R>=r)    //当前区间被查询区间完全包含     {        ans[x]+=k*(r-l+1);        lazytag[x]+=k;        return;    }    //不完全包含     pushdown(x,l,r);//处理懒标记，排除影响     ll mid=(l+r)>>1;    if(L<=mid)update(L,R,l,mid,leftchild(x),k);    if(R>mid) update(L,R,mid+1,r,rightchild(x),k);    pushup(x);}ll querysum(ll a,ll b,ll l,ll r ll x) {    ll res=0;    //当前区间被查询区间完全包含     if(a<=l && r<=b)return ans[p];     //不完全包含     ll mid=(l+r)>>1;    push_down(x,l,r);    if(a<=mid)res+=querysum(a,b,l,mid,leftchild(x));    if(b>mid) res+=querysum(a,b,mid+1,r,rightchild(x));    return res;}

接下来求和和更新的操作类似

都是判断所求区间与当前区间的包含关系

完全包含当前区间比较好办

不完全包含的情况用二分查找，降低时间复杂度owo

嘛

测试点信息