树状数组模板

Posted on | In | | Visitors:
Words count in article: 593

树状数组模板

算法细节没工夫写啦~~~

时间复杂度

树状数组和线段树都是 $nlogn$ ，但是，你会发现，在查询时，树状数组最好情况是$logn$（比如8个数，然后查询8），但是线段树是所有情况都是 $nlogn$，稍慢于树状数组。

空间复杂度

树状数组完胜于线段树，线段树要开2倍到4倍内存（推荐4倍），但是树状数组一倍就够了。

适用范围

树状数组区间、单点的查询修改完胜线段树，但是线段树之所以存在的理由是因为它能适用于很多方面，不仅仅是区间、单点的查询修改，还有标记等等，可以用于模拟、DP等等，而且空间经过离散化以后也可以相对压缩，所以适用范围线段树更加广一些。

1. 题目

洛谷P3374 【模板】树状数组 1

题目描述

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

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

输入格式

第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

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

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

输出格式

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

2. 树状数组模板

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
#include<iostream>
#include<string.h>
using namespace std;
#define N 5100
int tree[N], n;
inline int lowbit(int i) {
	return i & (-i);
}
void add(int i, int k) {
	while (i <= n) {
		tree[i] += k;
		i += lowbit(i);
	}
}
int sum(int i) {
	int ans = 0;
	while (i != 0) {
		ans += tree[i];
		i -= lowbit(i);
	}
	return ans;
}
int main() {
	memset(tree, 0, sizeof(tree));
	int m, op, temp1, temp2;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> temp1;
		add(i, temp1);
	}
	for (int i = 0; i < m; i++) {
		cin >> op >> temp1 >> temp2;
		switch (op)
		{
		case 1: {
			add(temp1, temp2);
			break;
		}
		case 2: {
			cout << sum(temp2) - sum(temp1 - 1) << endl;
			break;
		}
		}
	}
}