线段树(一)

题目描述

如题，已知一个数列，你需要进行下面两种操作：

1. 将某区间每一个数加上 k。
2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 n, ,m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第i 项的初始值。

接下来 m行每行包含 3 或 4 个整数，表示一个操作，具体如下：

1. 1 x y k：将区间 [x, y] 内每个数加上 k。
2. 2 x y：输出区间 [x, y]内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

in:

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

out:

11

8

20

类似于树状数组,对数据操作有nlogn的性能

 #include<bits/stdc++.h>
 #define N 1000010
 using namespace std;
 struct node
 {
     int l,r;
     long long data;
     long long lazy;
 }tree[N<<1];
 int a[N],n,m;
 void bulid(int num,int l,int r)//递归建树
 {
     tree[num].l=l;
     tree[num].r=r;
     if(l==r)
     {
         tree[num].lazy=a[l];
         return;
     }
     int mid=(l+r)>>1;
     bulid(num*2,l,mid);
     bulid(num*2+1,mid+1,r);
     tree[num].lazy=tree[num*2].lazy+tree[num*2+1].lazy;
 }
 void lazy_log(int num)//懒标记
 {
     if(tree[num].data)
     {
         tree[num*2].lazy+=tree[num].data*(tree[num*2].r-tree[num*2].l+1);
         tree[num*2+1].lazy+=tree[num].data*(tree[num*2+1].r-tree[num*2+1].l+1);
         tree[num*2].data+=tree[num].data;
         tree[num*2+1].data+=tree[num].data;
         tree[num].data=0;
     }
 }
 void change(int num,int x,int y,int z)//增
{
    if(x<=tree[num].l && y>=tree[num].r){
        tree[num].lazy+=(long long)z*(tree[num].r-tree[num].l+1);
        tree[num].data+=z;
        return;
    }
    lazy_log(num);
    int mid=(tree[num].l+tree[num].r)>>1;
    if(x<=mid) change(num*2,x,y,z);
    if(y>mid) change(num*2+1,x,y,z);
    tree[num].lazy=tree[num*2].lazy+tree[num*2+1].lazy;
}

long long ask(int num,int x,int y)//查
{
    if(x<=tree[num].l && y>=tree[num].r) return tree[num].lazy;
    lazy_log(num);
    int mid=(tree[num].l+tree[num].r)>>1;
    long long ans=0;
    if(x<=mid) ans+=ask(num*2,x,y);
    if(y>mid) ans+=ask(num*2+1,x,y);
    return ans;
}
 int main()
 {
     ios::sync_with_stdio(false);
     cin>>n>>m;
     for(int i=1;i<=n;i++)
     {
         cin>>a[i];
     }
     bulid(1,1,n);
     for(int i=1;i<=m;i++)
     {
         int k;
         cin>>k;
         if(k==1)
         {
             int x,y,z;
             cin>>x>>y>>z;
             change(1,x,y,z);
         }
         else
         {
             int x,y;
             cin>>x>>y;
             cout<<ask(1,x,y)<<endl;
         }
     }
     return 0;
 }