线段树整理

概述//每天整理一点，太多了  https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html#4175712（ORZ） POJ  3468 板子题 注意下数据范围 （因为int会爆，以后一定好好看题，浪费我10min....） http://poj.org/problem?id=3468 #include<iostream>//线段树题目集#inc

//每天整理一点，太多了 

https://www.cnblogs.com/TheRoadToTheGold/p/6254255.html#4175712（ORZ）

POJ  3468 板子题 注意下数据范围 （因为int会爆，以后一定好好看题，浪费我10min....）

http://poj.org/problem?id=3468

#include<iostream>//线段树题目集#include<cstdio>#include<cstring>using namespace std;const int maxn = 4e5 + 15;typedef long long ll;typedef struct{    ll l,r,sum,f;//sum为区间和,f为懒人标记}node;node Tree[maxn];//线段树ll n,q;ll _left,_right,value;voID buildTree(int l,int r,int cur){    Tree[cur].l = l;    Tree[cur].r = r;//左右区间范围    if(l==r)    {        scanf("%lld",&Tree[cur].sum);        return;    }    int mID = (l + r) >> 1;    buildTree(l,mID,cur*2);    buildTree(mID+1,cur<<1|1);    Tree[cur].sum = Tree[cur<<1].sum + Tree[cur<<1|1].sum; }//建树voID Down(int cur){    Tree[2*cur].f += Tree[cur].f;    Tree[2*cur+1].f += Tree[cur].f;    Tree[2*cur].sum += (Tree[2*cur].r - Tree[2*cur].l + 1)*Tree[cur].f;    Tree[2*cur+1].sum += (Tree[2*cur+1].r - Tree[2*cur+1].l + 1)*Tree[cur].f;    Tree[cur].f = 0;//因为已经传下去了,所以清零}//懒标记下传ll ans;voID ask_interval(int cur){    if(_left<=Tree[cur].l&&Tree[cur].r<=_right)    {        ans += Tree[cur].sum;        return;    }    if(Tree[cur].f)        Down(cur);//下传懒人标记    ll mID = (Tree[cur].l + Tree[cur].r) >> 1;//mID 中间值    if(_left<=mID)        ask_interval(cur<<1);    if(_right>mID)        ask_interval(cur<<1|1);  }voID change_interval(int cur){    if(_left<=Tree[cur].l&&Tree[cur].r<=_right)//if node 在区间范围内    {        Tree[cur].sum += (Tree[cur].r - Tree[cur].l + 1)*value;        Tree[cur].f += value;        return;    }    if(Tree[cur].f)        Down(cur);    ll mID = (Tree[cur].l + Tree[cur].r) >> 1;//mID 中间值    if(_left<=mID)        change_interval(cur<<1);    if(_right>mID)        change_interval(cur<<1|1);    Tree[cur].sum = Tree[cur<<1].sum + Tree[cur<<1|1].sum;//(important) 更新完后一定要更新sum的总和值  }//线段树区间修改int main(){    while(scanf("%lld%lld",&n,&q)==2)//写返回值,不然可能会有些很SB的output 超出limit    {        memset(Tree,sizeof(Tree));        buildTree(1,n,1);//1 ~ n为范围,cur 为当前节点        char cmd;        while(q--)        {            ans = 0;            getchar();            scanf("%c",&cmd);//区间查询,区间修改            scanf("%lld%lld",&_left,&_right);            if(cmd==‘Q‘)            {                   ask_interval(1);                cout<<ans<<endl;            }else{                scanf("%lld",&value);                change_interval(1);            }        }    }}

总结

以上是内存溢出为你收集整理的线段树整理全部内容，希望文章能够帮你解决线段树整理所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。