poj 3468 A Simple Problem with Integers 【线段树-成段更新】-白红宇

poj 3468 A Simple Problem with Integers 【线段树-成段更新】

阅读量：6265 次

发布时间：2019-06-22

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

题目：

题意：给出n个数。两种操作

1：l -- r 上的全部值加一个值val

2：求l---r 区间上的和

分析：线段树成段更新，成段求和

树中的每一个点设两个变量sum 和 num ，分别保存区间 l--r 的和和l---r 每一个值要加的值

对于更新操作：对于要更新到的区间上面的区间，直接进行操作加上（r - l +1）* val 。

以下的区间标记num += val

对于求和操作。每次进行延迟更新。把num值分别更新到两个子区间。sum值更新，然后num值变为0

注意：这个题目会超int 。

所以

AC代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const long long N = 110000;const long long inf = 0x3f3f3f3f;struct Node{ long long l,r; long long num,sum;};Node tree[5*N];long long a[N];long long cnt ;void build(long long o,long long l,long long r){ tree[o].l = l,tree[o].r = r; tree[o].num = 0; if(l==r) { tree[o].sum = a[cnt++]; return ; } long long mid = (l+r)/2; build(o+o,l,mid); build(o+o+1,mid+1,r); tree[o].sum = tree[o+o].sum + tree[o+o+1].sum;}void push_update(long long o){ if(tree[o].num!=0) { tree[o].sum += tree[o].num * (tree[o].r-tree[o].l+1); tree[o+o+1].num += tree[o].num; tree[o+o].num += tree[o].num; tree[o].num = 0; }}void update(long long o,long long l,long long r,long long val){ if(l==tree[o].l && r == tree[o].r) { tree[o].num += val; return ; } tree[o].sum += (val*(r-l+1)); //维护前面的 long long mid = (tree[o].l+tree[o].r) / 2; if(r<=mid) update(o+o,l,r,val); else if(l>mid) update(o+o+1,l,r,val); else { update(o+o,l,mid,val); update(o+o+1,mid+1,r,val); }}long long query(long long o,long long l,long long r){ if(tree[o].l==l && tree[o].r == r) { return tree[o].sum+(r-l+1)*tree[o].num; } push_update(o); //维护后面的 long long mid = (tree[o].l+tree[o].r)/2; if(r<=mid) return query(o+o,l,r); else if(l>mid) return query(o+o+1,l,r); else return query(o+o,l,mid) + query(o+o+1,mid+1,r);}int main(){ //freopen("Input.txt","r",stdin); long long n,m; while(~scanf("%lld%lld",&n,&m)) { cnt = 0; for(long long i=0;i