树状数组从入门到弃疗

标签：实现   查询   tail   ret   stdin   lowbit   add   span   位置   

树状数组是一类存储后缀和，更新后缀和，通过lowbit来限定后缀和的长度，利用二进制使得查询、更新的时间复杂度都在\(O(logn)\)的数据结构，码量十分小，常数优秀

注意：以下下代码部分未经过压力测试，不保证完全正确

单点修改+区间查询

树状数组 1

#include
#define int long long 
using namespace std;
const int N=1e6+2020;
int c[N],a[N],n,q;
int lowbit(int x) {
	return x&-x;
}
int sum(int r) {
	int ret=0;
	while(r>0) ret+=c[r],r-=lowbit(r);
	return ret;
}
void add(int x,int val) {
	while(x>n>>q;
	for(int i=1; i

区间修改，单点查询

树状数组 2

利用差分数组还原原数组的方法即可实现单点查询

显然差分数组可以快速修改区间

我是\(SB\)

/*
@ author:pyyyyyy/guhl37
-----思路------

-----debug-------

*/
#include
#define int long long
using namespace std;
const int N=5e6+2020;
int delta[N],n,q,a[N];
int lowbit(int x) {
	return x&(-x);
}
void add(int x,int val) {
	while(x>n>>q;
	for(int i=1; i

区间修改+区间查询

树状数组 3

对一个差分数组做一次前缀和可以得到每个位置的值再对每个位置累加一下就是一个区间的值

对于差分数组\(delta\)

差分数组的前缀和为\(val_i=\sum\limits_{j=1}^idelta_j\)

对于区间\([l,r]\)

\(s_{l,r}=\sum\limits_{i=1}^rval_i-\sum\limits_{i=1}^{l-1}val_i\)（前缀和相减的形式）

可以发现，一个区间的值实际上就是差分数组前缀和的前缀和做减法

我们可以用树状数组维护差分数组前缀和的前缀和

\(s_p=\sum\limits_{i=1}^p\sum\limits_{j=1}^idelta_j\)

\(s_p=\sum\limits_{i=1}^p\left(p-i+1\right)c_i=\left(p+1\right)\sum\limits_{i=1}^pc_i-\sum\limits_{i=1}^pi *c_i\)

显然这些东西都可用树状数组维护一下

/*
@ author:pyyyyyy/guhl37
-----思路------

-----debug-------
add里面为什么条件是
#define int long long
using namespace std;
const int N=2000005;
int n,q;
int lowbit(int x) {
	return x&-x;
}
void add(int *arr,int x,int val) {
	while(x>n>>q;
	for(int i=1; i>opt;
		if(opt==1) {
			scanf("%lld %lld %lld",&l,&r,&x);
			add(d,l,x),add(d,r+1,-x);
			add(id,l,(l-1)*x),add(id,r+1,-r*x);
		} else if(opt==2) {
			scanf("%lld %lld",&l,&r);
			cout

上面有个不太懂的地方，恳请大佬解答

区间最值

没想到树状数组能干这个 ，其实常数也蛮大的了，没什么意义，还不如写线段树

void build(int n){
	for(int i=1;i=lowbit(r)) ans=max(ans,c[r]),r-=lowbit(r);
	}
	return ans;
}

二维树状数组--单点修改，区间查询

二维树状数组 1

二维树状数组--区间修改，单点查询

二维树状数组 2

二维树状数组--区间修改，区间查询

二维树状数组 3

参考资料

树状数组简单易懂的详解

可以代替线段树的树状数组?——树状数组进阶

树状数组的区间修改，区间查询

树状数组 3 ：区间修改，区间查询

树状数组从入门到弃疗

标签：实现   查询   tail   ret   stdin   lowbit   add   span   位置   

原文地址：https://www.cnblogs.com/pyyyyyy/p/13190339.html