相关题目链接
- 线段树1
Solution
- 首先看到题目标题，我们就知道要用线段树，但这道题还可以用其他方法来AC，比如树状数组，不仅代码量少，而且常数还小，根据树状数组模板2我们知道，树状数组的区间修改是要用差分的，这点我的另一篇Blog介绍过，不懂的点击这。
- 接下来我们直接将如果用树状数组实现区间修改区间查询。我们用a数组表示原序列，d数组表示差分数组,我们可得 $\sum\limits_{i=1}^{p}a[i]=\sum\limits_{i=1}^{p}\sum\limits_{j=1}^{i}d[j]$ ,在右侧的式子中，$d[1]$被用了$p$次，$d[2]$被用了$p-1$次,我们可以推出位置p的前缀和
,我们可以维护两个数组前缀和$sum1[i]=d[i]$,另一个数组$sum2[i]=d[i]*i$ - 查询
位置$p$的前缀和即： $(p + 1) * sum1$数组中$p$的前缀和- sum2数组中p的前缀和。区间[l, r]的和即：位置r的前缀和 - 位置l的前缀和。 修改
对于sum1数组的修改同问题2中对$d$数组的修改。对于sum2数组的修改也类似，我们给 sum2[l] 加上 $l \times x$ ，给 sum2[r + 1] 减去
$(r + 1) \times x$。Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
typedef long long ll;
const int Maxn = 100000 + 10;
ll sc() {
ll xx = 0, ff = 1; char cch = gc;
while(!isdigit(cch)) {
if(cch == '-') ff = -1; cch = gc;
}
while(isdigit(cch)) {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
void out(ll x) {
if(x < 0) pc('-'), x = -x;
if(x >= 10)
out(x / 10);
pc(x % 10 + '0');
}
ll n, m;
ll sum1[Maxn], sum2[Maxn];
ll lowbit(ll x) {
return x & (-x);
}
void modify(ll x, ll num) {
for(int i = x; i <= n; i += lowbit(i))
sum1[i] += num, sum2[i] += num * x;
}
void update(ll x, ll y, ll num) {
modify(x, num);
modify(y + 1, -num);
}
ll ask(ll x) {
ll ans = 0;
for(int i = x; i; i -= lowbit(i))
ans += (x + 1) * sum1[i] - sum2[i];
return ans;
}
ll query(ll x, ll y) {
return ask(y) - ask(x - 1);
}
int main() {
n = sc(); m = sc();
for(int i = 1; i <= n; ++i)
update(i, i, sc());
while(m--) {
ll flag = sc(), x = sc(), y = sc();
if(flag == 1) {
ll num = sc();
update(x, y, num);
}
else {
out(query(x, y)), pc('\n');
}
}
return 0;
}
// Coded by dy.
rp++*