这是一道区间查询与修改的题目,首选树状数组线段树,但是根据《算法竞赛进阶指南》的思想,我们不妨思考一下树状数组的解法。👀
首先对不变量$A_{i}$求前缀和,最后在区间上累加改变量即可。那么问题来了,树状数组仅支持单点查询与修改,如何强行让它支持区间上的操作呢?
我们假设$t[i]$数组储存着每个点的改变量,那么对于$[1,x]$区间,有改变量$$change = \sum\limits_{i=1}^{x}\sum\limits_{j=1}^{i}b[j]=\sum\limits_{i=1}^{x}(x-i+1)*b[i]=(x+1)\sum\limits_{i=1}^{x}b[i]-\sum\limits_{i=1}^{x}i*b[i]$$
对应的我们维护两个树状数组,一个用于维护$(x+1)\sum\limits_{i=1}^{x}b[i]$,而另一个用于维护$\sum\limits_{i=1}^{x}i*b[i]$。
下面给出参考代码:
#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
using ll = long long;
int n,m;
ll sum[MAXN];
ll tree[2][MAXN];
int lowbit(int x) {
return x & -x;
}
void add(int k,int x,ll data) {
for (; x <= n; x += lowbit(x))
tree[k][x] += data;
}
ll query(int k,int x) {
ll ret = 0;
for (; x; x -= lowbit(x))
ret += tree[k][x];
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
int temp;
for (int i = 1; i <= n; ++i) {
cin >> temp;
sum[i] = sum[i - 1] + temp;
}
char op;
int l,r,d;
for (int i = 1; i <= m; ++i) {
cin >> op;
if (op == 'C') {
cin >> l >> r >> d;
add(0, l, d);
add(0, r + 1, -d);
add(1, l, l * d);
add(1, r + 1, (r + 1) * -d);
} else {
cin >> l >> r;
cout << sum[r] + (r + 1) * query(0, r) - query(1, r) - sum[l - 1] - l * query(0, l - 1) + query(1, l - 1) << endl;
}
}
return 0;
}
当然,这道题目理所应当可以用线段树做,参考代码如下:
#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
using ll = long long;
struct SegmentTree{
int l,r;
int data;
int add;
}t[MAXN << 2];
int n,m;
int a[MAXN];
void build(int p,int l,int r) {
t[p].l = l;
t[p].r = r;
if (l == r) {
t[p].data = a[l];
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
t[p].data = t[p << 1].data + t[p << 1 | 1].data;
}
void downpush(int p) {
if (t[p].add) {
t[p << 1].data += t[p].add * (t[p << 1].r - t[p << 1].l + 1);
t[p << 1 | 1].data += t[p].add * (t[p << 1 | 1].r - t[p << 1 | 1].l + 1);
t[p << 1].add += t[p].add;
t[p << 1 | 1].add += t[p].add;
t[p].add = 0;
}
}
void change(int p,int l,int r,int d) {
if (l <= t[p].l && r >= t[p].r) {
t[p].data += d * (t[p].r - t[p].l + 1);
t[p].add += d;
return;
}
downpush(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
change(p << 1, l, r, d);
if (r > mid)
change(p << 1 | 1, l, r, d);
t[p].data = t[p << 1].data + t[p << 1 | 1].data;
}
ll query(int p,int l,int r) {
ll ret = 0;
if (l <= t[p].l && r >= t[p].r)
return t[p].data;
downpush(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
ret += query(p << 1, l, r);
if (r > mid)
ret += query(p << 1 | 1, l, r);
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
build(1, 1, n);
char op;
int l,r,d;
for (int i = 1; i <= m; ++i) {
cin >> op;
if (op == 'C') {
cin >> l >> r >> d;
change(1, l, r, d);
} else {
cin >> l >> r;
cout << query(1, l, r) << endl;
}
}
return 0;
}
(线段树的代码就是长
One comment
👀