【模板】线段树 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 k k k。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数 n , m n, m n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n n n 个用空格分隔的整数，其中第 i i i 个数字表示数列第 i i i 项的初始值。
接下来 m m m 行每行包含 3 3 3 或 4 4 4 个整数，表示一个操作，具体如下：
1 x y k：将区间 [ x , y ] [x, y] [x,y] 内每个数加上 k k k。2 x y：输出区间 [ x , y ] [x, y] [x,y] 内每个数的和。
输出格式
输出包含若干行整数，即为所有操作 2 的结果。
样例 #1
样例输入 #1
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
样例输出 #1
11
8
20
提示
对于
30
%
30\%
30% 的数据：
n
≤
8
n \le 8
n≤8，
m
≤
10
m \le 10
m≤10。
对于
70
%
70\%
70% 的数据：
n
≤
10
3
n \le {10}^3
n≤103，
m
≤
10
4
m \le {10}^4
m≤104。
对于
100
%
100\%
100% 的数据：
1
≤
n
,
m
≤
10
5
1 \le n, m \le {10}^5
1≤n,m≤105。
保证任意时刻数列中所有元素的绝对值之和 ≤ 10 18 \le {10}^{18} ≤1018。
【样例解释】
AC代码：
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<string>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<numeric>
#include<iomanip>
#define endl '\n'
//#define x first
//#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int>PII;
const int N=3e5+10;
const int MOD=1e9 + 7;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e6 + 10;
ll tree1[M], tree2[M];//此时树状数组维护的是差分数组
int n, m;
int bit(int x)
{
return x & -x;
}
void add(ll tree[], int i, int x)
{
while(i <= n)
{
tree[i] += x;
i += bit(i);
}
}
ll sum(ll tree[],int i)
{
ll res = 0;
while(i > 0)
{
res += tree[i];
i -= bit(i);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
int x;
cin >> x;
add(tree1, i, x);
add(tree1, i + 1, -x);
add(tree2, i, (i - 1) * x);
add(tree2, i + 1, -(i * x));
}
while(m --){
int a, x, y, k;
cin >> a;
if(a == 1)
{
cin >> x >> y >> k;
add(tree1, x, k);
add(tree1, y + 1, -k);
add(tree2, x, (x - 1) * k);
add(tree2, y + 1, -(y * k));
}
if(a == 2)
{
cin >> x >> y;
ll s = sum(tree1, y) * y - sum(tree2, y) - sum(tree1, x - 1) * (x - 1) + sum(tree2, x - 1);//注意去括号要变号
cout << s << endl;
}
}
return 0;
}