2022年11月13日 开学第十周树状数组

目录

一：个人对树状数组的理解

二：树状数组可以解决的问题：

三：个人感受

四：下周

---

一：个人对树状数组的理解

树状数组是将二叉树的节点换成数组的一种数据结构，但和二叉树在某些方面又有很大差别。因为我要看到了树状数组套权值线段树，我看不太明白，所以分开学，先学习树状数组。

二：树状数组可以解决的问题：

1：单点查询和修改

2：区间查询修改

3：单点查询后区间修改

三：个人感受

最大的感觉就是树状数组写起来比线段树简单，代码实现快。（似乎速度也更快）

但是感觉对个人口算能力要求比较高，那个位运算！！！

P3374 【模板】树状数组 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 

#include
int * c, n;
 
int lowbit(int x) {
	return x & -x;
}
 
void add(int x, int k) {
	for (int i = x; i <= n; i += lowbit(i)) {
		c[i] += k;
	}
}
 
int sum(int x) {
	int result = 0;
	for (int i = x; i > 0; i -= lowbit(i)) {
		result += c[i];
	}
	return result;
}
 
int main() {
	int m, i, cmd, x, y;
	scanf("%d %d", &n, &m);
	c = (int *)malloc((n + 1) * sizeof(int));
	for (i = 1; i <= n; i++) c[i] = 0;
	for (i = 1; i <= n; i++) {
		scanf("%d", &x);
		add(i, x);
	}
	for (i = 0; i < m; i++) {
		scanf("%d %d %d", &cmd, &x, &y);
		if (cmd == 1) {
			add(x, y);
		}
		else {
			printf("%d\n", sum(y) - sum(x - 1));
		}
	}
	free(c);
	return 0;
}

P3368 【模板】树状数组 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include
int * c, n;
 
int lowbit(int x) {
	return x & -x;
}
 
void add(int x, int k) {
	for (; x <= n; x += lowbit(x)) {
		c[x] += k;
	}
}
 
int sum(int x) {
	int result = 0;
	for (; x > 0; x -= lowbit(x)) {
		result += c[x];
	}
	return result;
}
 
int main() {
	int m, i, cmd, x, y, k, tmp = 0;
	scanf("%d %d", &n, &m);
	c = (int *)malloc((n + 1) * sizeof(int));
	for (i = 1; i <= n; i++) c[i] = 0;
	for (i = 1; i <= n; i++) {
		scanf("%d", &x);
		if (i != 1) {
			x -= tmp;
		}
		tmp += x;
		add(i, x);
	}
	for (i = 0; i < m; i++) {
		scanf("%d", &cmd);
		if (cmd == 1) {
			scanf("%d %d %d", &x, &y, &k);
			add(x, k);
			add(y + 1, -k);
		}
		else {
			scanf("%d", &x);
			printf("%d\n", sum(x));
		}
	}
	free(c);
	return 0;
}

四：下周

下周争取学习完树状数组套权值线段树