APTX Blog

A Moe Blog Set Up By APTX

#C/C++#数据结构:一维树状数组/二维树状数组模板

文章目录[隐藏]

模板

#define lowbit(x) x & -x
//1D
void add(int x,int t) {
	while(x <= n) {
		v[x] += t;
		x += lowbit(x);	
	}
}

int query(int x) {
	int res = 0;
	while(x) {
		res += v[x];
		x -= lowbit(x);
	}
	return res;
}

//2D n * m

void add(int x,int y,int t) {
	while(x <= n) {
		for(int k = y;k <= m;k += lowbit(k))
			v[x][k] += t;
		x += lowbit(x);
	}
}

int query(int x,int y) {
	int res = 0;
	while(x) {
		for(int k = y;k;k -= lowbit(k))
			res += v[x][k];
		x -= lowbit(x);
	}
	return res;
}

 

点赞

发表评论

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