APTX Blog

A Moe Blog Set Up By APTX

#C/C++#树状数组模板

问题模型

现在有一个这样的问题:有一个数组a,,现在给你w次修改,q次查询,修改的话是修改数组中某一个元素的值;查询的话是查询数组中任意一个区间的和。

这个问题很常见,首先分析下朴素做法的时间复杂度,修改是O(1)的时间复杂度,而查询的话是O(n)的复杂度,总体时间复杂度为O(qn)

可能你会想到前缀和来优化这个查询,我们也来分析下,查询的话是O(1)的复杂度,而修改的时候修改一个点,那么在之后的所有前缀和都要更新,所以修改的时间复杂度是O(n),总体时间复杂度还是O(qn)。

可以发现,两种做法中,要么查询是O(1),修改是O(n);要么修改是O(1),查询是O(n)。那么就有没有一种做法可以综合一下这两种朴素做法,然后整体时间复杂度可以降一个数量级呢?有的,对,就是树状数组。

lowbit函数

int lobit(int k) {
	return k & (-k);
}

lowbit这个函数的功能就是求某一个数的二进制表示中最低的一位1

树状数组

这是树状数组的模型

《#C/C++#树状数组模板》

可以看出

C1 = A1
C2 = A1+A2
C3 = A3
C4 = A1+A2+A3+A4
C5 = A5
C6 = A5+A6
C7 = A7
C8 = A1+A2+A3+A4+A5+A6+A7+A8

通过lowbit函数来得出k,其中k就是该值从末尾开始0的个数。然后将其得出的结果加上x自身就可以得出当前节点的父亲节点的位置或者是x减去其结果就可以得出上一个父亲节点的位置。

所以他就变成logn的数据结构了

模板

树状数组 1

题目描述

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

1.将某一个数加上x

2.求出某区间每一个数的和

输入输出格式

输入格式:

第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

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

接下来M行每行包含3个整数,表示一个操作,具体如下:

操作1: 格式:1 x k 含义:将第x个数加上k

操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和

输出格式:

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

输入输出样例

输入样例#1:

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

输出样例#1:

14
16

代码

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 500005;
int a[maxn];
int n,m; 

int lowbit(int );
void add(int ,int );
int sum(int );

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
   	for(int i = 1;i <= n;++i) {
   		int t;
   		cin >> t;
   		add(i,t);
	}
   	for(int i = 1;i <= m;++i) {
   		int t,x,y;
   		cin >> t >> x >> y;
   		if(t == 1) add(x,y);
   		if(t == 2) cout << sum(y) - sum(x-1) << endl;
	}
	return 0;
}

int lobit(int k) {
	return k & (-k);
}
void add(int i,int t) {
	while(i <= n) {
		a[i] += t;
		i += lobit(i);
	}
}
int sum(int i) {
	int ans = 0;
	while(i) {
		ans += a[i];
		i -= lobit(i); 
	}
	return ans;
}

树状数组 2

题目描述

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

1.将某区间每一个数数加上x

2.求出某一个数的和

输入输出格式

输入格式:

第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。

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

接下来M行每行包含2或4个整数,表示一个操作,具体如下:

操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k

操作2: 格式:2 x 含义:输出第x个数的值

输出格式:

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

输入输出样例

输入样例#1:

5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4

输出样例#1:

6
10

代码

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int maxn = 500005;
int a[maxn];
int n,m; 
int low;

int lowbit(int );
void add(int ,int );
int sum(int );

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
   	for(int i = 1;i <= n;++i) {
   		int t;
   		cin >> t;
   		add(i,t - low);
   		low = t;
	}
   	for(int i = 1;i <= m;++i) {
   		int t;
   		cin >> t;
   		if(t == 1) {
   			int x,y,s;
   			cin >> x >> y >> s;
   			add(x,s);
   			add(y + 1,-s);
		}
   		if(t == 2) {
   			int s;
   			cin >> s;
   			cout << sum(s) <<endl;
		}
	}
	return 0;
}

int lobit(int k) {
	return k & (-k);
}
void add(int i,int t) {
	while(i <= n) {
		a[i] += t;
		i += lobit(i);
	}
}
int sum(int i) {
	int ans = 0;
	while(i) {
		ans += a[i];
		i -= lobit(i); 
	}
	return ans;
}

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注