poj 3468 A Simple Problem with Integers 树状数组

缘起

问题: 给你一个数列,每次询问(Q)一个区间的和,或者每次将一个区间的所有元素都加上(A)一个数.数列的项数不超过10万,每个数的范围是正负十亿之间,要处理的询问次数不超过10万条.

传送门

分析

【1】中和此题唯一的不同在于【1】中要求输出的是每个数字，而本题要求输出的是部分和. 我们可以沿用一样的思想，就是只专注于累计的改变量以及只专注于 a[i,…,n]+val 导致的改变量（后面做一次反向操作即可）.

设b[i]是a[i,…,n]+val导致a[i]的增量（就是题目中说的(a,b,c)中的c）, 则b[1,…,i]的部分和就是a[i]最后累计的增量. 而s[i](部分和序列)的增量是a[1]、…、a[i]的增量之和, 即 b[1]+(b[1]+b[2])+…+(b[1]+…+b[i]) = ib[1]+(i-1)\b[2]+…+b[i] = (i+1)*b[1,..,i]部分和-(b[1]+2*b[2]…+i*b[i]), 所以s[i]的累积增量就是(i+1)*b[i]的部分和减去{i*b[i]}的部分和. 因此我们在进行a[i,…,n]+val的同时需要维护两个树状数组. 

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
64
65
66
67
68
69
70
71
72
73
74
75
76
#include "stdafx.h"
#include <iostream>
#define LOCAL
using namespace std;
typedef long long LL;
const int MAX_N = 100000+5;
int n,q, a[MAX_N];
LL b[MAX_N], c[MAX_N],S[MAX_N]; // 0索引都不用于存储数据, b和c是分析中要维护的两个树状数组, s是a的部分和序列, n是数字的个数, q是query的个数

inline int lowbit(int x) {return x&(-x);}

void update(int x, int val) // a[x,...,n]+val, 需要维护两个树状数组b和c
{
	if (x>n) return;
	int i = x;
	while(i<=n) // 维护b
	{
		b[i] += val;
		i+=lowbit(i);
	}
	i = x;
	while(i<=n) // 维护c
	{
		c[i] += x*val;
		i+=lowbit(i);
	}
}

LL partialsum(int x) // 获取分析中 a[1,...,x]的部分和的增量
{
	LL sum1 = 0, sum2 = 0; // 根据分析, sum = sum1*(x+1) - sum2, 而sum1和sum2就需要使用树状数组以logn为代价求取
	int t = x;
	while(t)
	{
		sum1+=b[t];
		t-=lowbit(t);
	}
	t = x;
	while(t)
	{
		sum2+=c[t];
		t-=lowbit(t);
	}
	return sum1*(x+1) - sum2;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &q);
	for (int i = 1; i<=n; i++)
	{
		scanf("%d", a+i);
		S[i] = S[i-1]+a[i];
	}
	while(q--)
	{
		getchar(); // 吸收多余换行符
		int s,e,val;
		if (getchar() == 'C')
		{
			scanf("%d%d%d", &s, &e, &val); // a[s,...,e]+val
			update(s, val);
			update(e+1, -val); // 反向操作
		}
		else
		{
			scanf("%d%d", &s, &e); // 需要查询 a[s,e]中的部分和
			printf("%lld\n", S[e]+partialsum(e) - S[s-1] - partialsum(s-1));
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 1047ms
Memory 2896kB
Length 1309
Lang C++
Submitted 2019-06-06 13:22:25
RemoteRunId 20297410

参考

【1】https://yfsyfs.github.io/2019/06/06/%E7%96%AF%E7%8B%82%E7%9A%84%E5%8C%BA%E9%97%B4-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/

【2】https://yfsyfs.github.io/2019/06/05/poj-2481-Cows-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/