本文共 2992 字，大约阅读时间需要 9 分钟。

P3374【模板】树状数组1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

• 将某一个数加上 $x$
• 求出某区间每一个数的和

输入格式

第一行包含两个正整数 $n,m$ ，分别表示该数列数字的个数和操作的总个数。第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：

• 1 x k 含义：将第 $x$ 个数加上 $k$
• 2 x y 含义：输出区间 $[x,y]$ 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例

输入 #1

5 51 5 4 2 31 1 32 2 51 3 -11 4 22 1 4

输出 #1

1416

说明/提示

【数据范围】 对于 $30\%$ 的数据，$1\le n\le 8，1\le m\le 10$ ； 对于 70% 的数据，$1\le n,m\le 10^4$ ； 对于 100% 的数据，$1\le n,m\le 5\times 10^5$ 。

思路1：使用树状数组，代码如下：

#include 
   
    using namespace std;#define lowbit(x) ((x) & (-x))typedef long long ll;const int MAXN = 5e5 + 10;ll tree[MAXN], n, m, t, a, b;inline void add(ll i, ll d) {
   	while (i <= n) {
   		tree[i] += d;		i += lowbit(i);		}}inline ll sum(ll i) {
   	ll ret = 0;	while (i) {
   		ret += tree[i];		i -= lowbit(i);		}	return ret;}inline ll query(ll x, ll y) {
   	return sum(y) - sum(x - 1);}int main() {
    	scanf("%lld%lld", &n, &m);	memset(tree, 0, sizeof(tree));	for (int i = 1; i <= n; ++i) {
   		scanf("%lld", &t);		add(i, t); 	}	for (int i = 1; i <= m; ++i) {
    		scanf("%lld%lld%lld", &t, &a, &b);		if (t == 1) add(a, b);		else printf("%lld\n", query(a, b));	}    return 0;}
   

---

P3368【模板】树状数组2

题目描述

如题，已知一个数列，你需要进行下面两种操作：

• 将某区间每一个数加上 $x$
• 求出某一个数的值。

输入格式

第一行包含两个整数 $N、M$ ，分别表示该数列数字的个数和操作的总个数。 第二行包含 $N$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。 接下来 $M$ 行每行包含 $2$ 或 $4$ 个整数，表示一个操作，具体如下： 操作 $1$ ： 格式：1 x y k 含义：将区间 $[x,y]$ 内每个数加上 $k$ ； 操作 $2$ ： 格式：2 x 含义：输出第 $x$ 个数的值。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例

输入 #1

5 51 5 4 2 31 2 4 22 31 1 5 -11 3 5 72 4

输出 #1

610

说明/提示

数据规模与约定： 对于 $30\%$ 的数据：$N\le 8,M\le 10$ ； 对于 $70\%$ 的数据：$N\le 10000,M\le 10000$ ； 对于 $100\%$ 的数据：$1\le N,M\le 500000$ ，$1\le x,y\le n$ ，保证任意时刻序列中任意元素的绝对值都不大于 $2^{30}$ 。

思路1：使用树状数组的扩展，代码如下：

#include 
   
    using namespace std;#define lowbit(x) ((x) & (-x))typedef long long ll;const int maxn = 5e5 + 10;ll tree[maxn], n, m, k; inline void add(int i, ll d) {
    	while (i <= n) {
   		tree[i] += d;		i += lowbit(i);	}}inline void addRange(int a, int b, ll c) {
    //区间修改 	add(a, c);   	add(b + 1, -c);}inline int sum(int i) {
   	//前缀和查询(单点查询) 	int ret = 0;	while (i) {
   		ret += tree[i];		i -= lowbit(i);	}	return ret;}int main() {
    	scanf("%lld%lld", &n, &m);	memset(tree, 0, sizeof(tree));	ll pre = 0, now; 	for (int i = 1; i <= n; ++i) {
   		scanf("%lld", &now);		add(i, now - pre);	//维护差分数组 		pre = now;	}	int l, r, op;	for (int i = 1; i <= m; ++i) {
   		scanf("%d", &op);		if (op == 1) {
    //把区间[l,r]内的每个数加上k			scanf("%d%d%lld", &l, &r, &k);			addRange(l, r, k); //区间修改		} 		else if (op == 2) {
    //输出第k个数的值			scanf("%d", &k);			printf("%lld\n",  sum(k));		}	}    return 0;}
   

转载地址：https://memcpy0.blog.csdn.net/article/details/108408616 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！