题目
题目描述
给定数列 \(a[1],a[2], \dots,a[n]\) ，你需要依次进行q个操作，操作有两类：
1 l r x：给定l,r,x，对于所有 \(i \in[l,r]\) ，将a[i]加上x（换言之，将 \(a[l],a[l+1], \dots,a[r]\) 分别加上x）；
2 l r：给定l,r，求 \(\sum_{i=l}^ra[i]\) 的值（换言之，求 \(a[l]+a[l+1]+ \dots+a[r]\) 的值）。
输入描述
第一行包含2个正整数n,q，表示数列长度和询问个数。保证 \(1 \le n,q \le10^6\) 。
第二行n个整数 \(a[1],a[2], \dots,a[n]\) ，表示初始数列。保证 \(|a[i]| \le10^6\) 。
接下来q行，每行一个操作，为以下两种之一：
1 l r x：对于所有 \(i \in[l,r]\) ，将a[i]加上x；
2 l r：输出 \(\sum_{i=l}^ra[i]\) 的值。保证 \(1 \le l \le r \le n\) , \(|x| \le10^6\) 。
输出描述
对于每个2lr操作，输出一行，每行有一个整数，表示所求的结果。
示例1
输入
5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4
输出
15
34
32
33
50
备注
对于所有数据，\(1 \le n,q \le10^6\) , \(|a[i]| \le10^6\) , \(1 \le l \le r \le n\) , \(|x| \le10^6\) 。
题解
方法一
知识点：线段树。
可以用线段树，不过因为线段树空间常数是四倍，容易炸空间，但还是有概率能过。
时间复杂度 \(O((n+q)\log n)\)
空间复杂度 \(O(n)\)
方法二
知识点：树状数组。
本题正解，是用树状数组维护区间和、区间加，是个板子题。
设原数组为 \(a\) ，差分数组为 \(d\) ，有如下公式：
\[\begin{aligned} sum_{1,x} &= \sum_{i=1}^{x} a_i \\ &= \sum_{i=1}^{x} \sum_{j=1}^{i} d_j \\ &= \sum_{j=1}^{x} \sum_{i=j}^{x} d_j \\ &= \sum_{j=1}^{x} (x-j+1)d_j \\ &= (x+1) \sum_{j=1}^{x} d_j - \sum_{j=1}^{x} jd_j \\ \end{aligned} \]因此只需要维护 \(d_j\) 和 \(jd_j\) 的前缀和即可。同时，在差分意义下，区间加转化为两次单点加。
时间复杂度 \(O((n+q)\log n)\)
空间复杂度 \(O(n)\)
代码
方法一
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct T {
int len;
ll sum;
static T e() { return { 0,0 }; }
friend T operator+(const T &a, const T &b) { return { a.len + b.len, a.sum + b.sum }; }
};
struct F {
ll add;
static F e() { return { 0 }; }
T operator()(const T &x) { return { x.len,x.sum + add * x.len }; }
F operator()(const F &g) { return { g.add + add }; }
};
template<class T, class F>
class SegmentTreeLazy {
int n;
vector<T> node;
vector<F> lazy;
void push_down(int rt) {
node[rt << 1] = lazy[rt](node[rt << 1]);
lazy[rt << 1] = lazy[rt](lazy[rt << 1]);
node[rt << 1 | 1] = lazy[rt](node[rt << 1 | 1]);
lazy[rt << 1 | 1] = lazy[rt](lazy[rt << 1 | 1]);
lazy[rt] = F::e();
}
void update(int rt, int l, int r, int x, int y, F f) {
if (r < x || y < l) return;
if (x <= l && r <= y) return node[rt] = f(node[rt]), lazy[rt] = f(lazy[rt]), void();
push_down(rt);
int mid = l + r >> 1;
update(rt << 1, l, mid, x, y, f);
update(rt << 1 | 1, mid + 1, r, x, y, f);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
}
T query(int rt, int l, int r, int x, int y) {
if (r < x || y < l)return T::e();
if (x <= l && r <= y) return node[rt];
push_down(rt);
int mid = l + r >> 1;
return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);
}
public:
SegmentTreeLazy(int _n = 0) { init(_n); }
SegmentTreeLazy(const vector<T> &src) { init(src); }
void init(int _n) {
n = _n;
node.assign(n << 2, T::e());
lazy.assign(n << 2, F::e());
}
void init(const vector<T> &src) {
assert(src.size());
init(src.size() - 1);
function<void(int, int, int)> build = [&](int rt, int l, int r) {
if (l == r) return node[rt] = src[l], void();
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
};
build(1, 1, n);
}
void update(int x, int y, F f) { update(1, 1, n, x, y, f); }
T query(int x, int y) { return query(1, 1, n, x, y); }
};
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
vector<T> a(n + 1);
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
a[i] = { 1,x };
}
SegmentTreeLazy<T, F> sgt(a);
while (q--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
int x;
cin >> x;
sgt.update(l, r, { x });
}
else cout << sgt.query(l, r).sum << '\n';
}
return 0;
}
方法二
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct T {
ll sum;
static T e() { return { 0 }; }
T &operator+=(const T &x) { return sum += x.sum, *this; }
};
template<class T>
class Fenwick {
int n;
vector<T> node;
public:
Fenwick(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
node.assign(n + 1, T::e());
}
void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }
T query(int x) {
T ans = T::e();
for (int i = x;i >= 1;i -= i & -i) ans += node[i];
return ans;
}
};
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
Fenwick<T> d(n + 1), di(n + 1);
auto update = [&](int l, int r, T val) {
d.update(l, { val.sum }), d.update(r + 1, { -val.sum });
di.update(l, { l * val.sum }), di.update(r + 1, { -(r + 1) * val.sum });
};
auto query = [&](int l, int r) {
return ((r + 1) * d.query(r).sum - di.query(r).sum) -
(l * d.query(l - 1).sum - di.query(l - 1).sum);
};
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
update(i, i, { x });
}
while (q--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
int x;
cin >> x;
update(l, r, { x });
}
else cout << query(l, r) << '\n';
}
return 0;
}