题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某一个数加上x
2.求出某区间每一个数的和
输入格式
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3个整数，表示一个操作，具体如下：
操作1： 格式：1 x k 含义：将第x个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式
输出包含若干行整数，即为所有操作2的结果。
输入输出样例
输入 #15 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 411
8
20说明/提示
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=10000，M<=10000
对于100%的数据：N<=500000，M<=500000
样例解释：
不解释了，线段树模板，需要用懒标记
AC代码
#include<iostream>
using namespace std;
const int N =100010;
struct no {
int r;
int l;
long long sum;
long long lz;
}tr[4*N];
long long ans = 0;
long long a[N];
int m, n;
void build(int i, int l, int r)
{
tr[i].l = l;
tr[i].r = r;
if (tr[i].l == tr[i].r)//叶子节点
{
tr[i].sum = a[tr[i].l];
return;
}
int mid = (l+r) >> 1;
build(i << 1, l,mid);
build((i << 1) + 1,mid + 1,r);
tr[i].sum = tr[i << 1].sum + tr[(i << 1)+ 1].sum;
}//建完全树
void push_down(int i)
{
if (tr[i].lz != 0)
{
tr[i << 1].lz += tr[i].lz;
tr[(i << 1) + 1].lz += tr[i].lz;//分给子节点
int mid = (tr[i].l + tr[i].r) >> 1;
tr[i << 1].sum += tr[i].lz * (mid - tr[i <<1].l + 1);
tr[(i << 1) + 1].sum += tr[i].lz * (tr[(i << 1) + 1].r - mid);
tr[i].lz = 0;//父节点归0
}
return;
}
void add(int i, int l, int r, long long k)
{
if (tr[i].l >= l && tr[i].r <= r)//完全包含
{
tr[i].sum += k * (tr[i].r- tr[i].l + 1);
tr[i].lz += k;
return;
}
push_down(i);//向下传递
if (tr[i << 1].r >= l)
add(i << 1, l, r, k);
if (tr[(i << 1) + 1].l <= r)
add((i << 1) + 1,l, r,k);
tr[i].sum = tr[i << 1].sum + tr[(i << 1) + 1].sum;
return;
}
long long search(int i, int l, int r)
{
if (tr[i].l >= l && tr[i].r <= r)//叶子节点
return tr[i].sum;
if (tr[i].r<l || tr[i].l>r)//不包含
return 0;
push_down(i);
long long s = 0;
if (tr[i << 1].r >= l)
s += search(i << 1, l, r);
if (tr[(i << 1) + 1].l <= r)
s += search((i << 1) + 1, l, r);
return s;
}
int main()
{
cin >> m >> n;
for (int i = 1; i <= m; i++)
{
cin >> a[i];
}
build(1, 1, m);
for (int i = 1; i <= n; i++)
{
int c;
cin >> c;
if (c == 1)
{
int x, y, z;
cin >> x >> y >> z;
add(1, x, y, z);
}
if (c == 2)
{
ans = 0;
int x, y;
cin >> x >> y;
ans=search(1, x, y);
cout << ans << endl;
}
}
return 0;
}//记得开long long 哦，好几次wa都是因为long long