树状数组+差分(另外这题卡常,用线段树会超时)
题意:给你一个数列,有两种操作:1.是把一个区间上每一个数加上x;2.输出一个区间的和。
思路:树状数组+差分。树状数组支持单点修改,所有用差分知识,修改单点以修该区间。问题在于,修该后如何维护差分数列以及用不超限的时间算出区间和。用两个数列维护答案,tree[i]是差分的树状数组,而tree1[i]存(x-1)tree[i],x是进行差分的节点下标。这样算答案的时候直接xtree[i]-tree1[i],这样就有1个d[x],2个d[x-1],3个d[x-2]…x-1个d1就是把差分数列求了前缀和。
code:
#include<iostream>
#define int long long//懒得改了,全变long long算了
#define endl '\n'//这里加快了几倍速度,没有就超时
using namespace std;
typedef long long LL;
const int N = 1e6 + 10; int n, q;
int a[N], tree[N], tree1[N];
int lowbit(int x) {
return x & (-x);
}
void add(int i, int j, int x) {//建立树状数组
for (int k = i; k <= n; k += lowbit(k))//差分步骤
tree[k] += x, tree1[k] += x * (i - 1);
for (int k = j + 1; k <= n; k += lowbit(k))
tree[k] -= x, tree1[k] -= x * (j);
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) {
res += x*tree[i] - tree1[i];
}
return res;
}
void solve() {
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
add(i,i,a[i]);
}
while (q--) {
int op;
int l, r;
int x;
cin >> op;
if (op == 1) {
cin >> l >> r >> x;
add(l,r,x);
}
else {
cin >> l >> r;
cout << query(r) - query(l - 1) << endl;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}