树状数组学习

树状数组主要用于处理：单点修改区间查询 的问题

如上图
可以看得出来，如果$x\equiv 0\left(\mathrm{mod}{2}^n\right)$，$n$取最大整数值，那么$c_x$管理的区间长度为$2^n$
$n$也是$x$最低位的$1$右边的$0$的个数

取最低位的$1$，可以用

//最低位1
int lowbit(int x) {
	return x & -x;
}

所以$c_x$管理的区间为$\left[x-lowbit(x)+1,x\right]$

单点修改

//a[x] += k
void add(int x, int k) {
	while (x <= n) {
		c[x] += k;
		x += lowbit(x);
	}
}

前缀和

//a[1]+a[2] + ... +a[x]
int query(int x) {
	int ans = 0;
	while (x >= 1) {
		ans += c[x];
		x -= lowbit(x);
	}
	return ans;
}

建树

//建树
void init() {
	int temp, j;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &temp);
		c[i] += temp;
		j = i + lowbit(i);
		if (j <= n)c[j] += c[i];
	}
}

洛谷P3374

单点修改+单点查询

#include<cstdio>

const int N = 5e5 + 5;
int c[N];//树状数组
int n;//长度

//最低位1
int lowbit(int x) {
	return x & -x;
}

//建树
void init() {
	int temp, j;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &temp);
		c[i] += temp;
		j = i + lowbit(i);
		if (j <= n)c[j] += c[i];
	}
}

//a[x] += k
void add(int x, int k) {
	while (x <= n) {
		c[x] += k;
		x += lowbit(x);
	}
}

//a[1]+a[2] + ... +a[x]
int query(int x) {
	int ans = 0;
	while (x >= 1) {
		ans += c[x];
		x -= lowbit(x);
	}
	return ans;
}

int main() {
	int m, x, y, z;
	scanf("%d%d", &n, &m);
	init();
	while (m--) {
		scanf("%d%d%d", &x, &y, &z);
		if (x == 1) {
			add(y, z);
		}
		else {
			printf("%d\n", query(z) - query(y - 1));
		}
	}
	return 0;
}

洛谷P3368

区间修改+区间查询
利用差分
$b[i]=a[i]-a[i-1]$
给$[l,r]$加上$x$，则$b[l]=b[l]+x,b[r+1]=b[r+1]-x$,其他位置没有变化

#include<cstdio>

const int N = 500005;

int d[N];//差分树状数组
int n;

int lowbit(int x) {
	return x & -x;
}

void init() {
	int temp, j, pre = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &temp);
		d[i] += temp - pre;
		pre = temp;
		j = i + lowbit(i);
		if (j <= n)d[j] += d[i];
	}
}

void add(int x, int k) {
	while (x <= n) {
		d[x] += k;
		x += lowbit(x);
	}
}

void range_add(int l, int r, int k) {
	add(l, k);
	add(r + 1, -k);
}

int query(int x) {
	int ans = 0;
	while (x >= 1) {
		ans += d[x];
		x -= lowbit(x);
	}
	return ans;
}

int main() {
	int m, t, x, y, z;
	scanf("%d%d", &n, &m);
	init();
	while (m--) {
		scanf("%d%d", &t, &x);
		if (t == 1) {
			scanf("%d%d", &y, &z);
			range_add(x, y, z);
		}
		else {
			printf("%d\n", query(x));
		}
	}
	return 0;
}

LOJ131

区间修改+区间求和
$$\begin{array}{rl}& \sum _{i=1}^r{a}_i\\ =& \sum _{i=1}^r\sum _{j=1}^i{b}_j\\ =& \sum _{i=1}^r{b}_i\times \left(r-i+1\right)\\ =& \sum _{i=1}^r{b}_i\times \left(r+1\right)-\sum _{i=1}^r{b}_i\times i\end{array}$$
因此可以维护$b_i$和$b_i\times i$

#include<cstdio>

typedef long long LL;
const int N = 6e6 + 5;

LL d1[N]; //差分树状数组
LL d2[N]; //差分*i树状数组
int n;

int lowbit(int x) {
	return x & -x;
}

void init() {
	LL temp, pre = 0;
	int j;
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &temp);
		d1[i] += temp - pre;
		d2[i] += i * (temp - pre);
		pre = temp;
		j = i + lowbit(i);
		if (j <= n) {
			d1[j] += d1[i];
			d2[j] += d2[i];
		}
	}
}

void add(int x, int k) {
	LL k2 = 1LL * x * k;
	while (x <= n) {
		d1[x] += k;
		d2[x] += k2;
		x += lowbit(x);
	}
}

void range_add(int l, int r, int k) {
	add(l, k);
	add(r + 1, -k);
}

LL get_sum(LL d[], int x) {
	LL ans = 0;
	while (x >= 1) {
		ans += d[x];
		x -= lowbit(x);
	}
	return ans;
}

LL query(int l, int r) {
	return (r + 1) * get_sum(d1, r) - l * get_sum(d1, l - 1) - get_sum(d2, r) + get_sum(d2, l - 1);
}

int main() {
	int m, t, x, y, z;
	scanf("%d%d", &n, &m);
	init();
	while (m--) {
		scanf("%d%d%d", &t, &x, &y);
		if (t == 1) {
			scanf("%d", &z);
			range_add(x, y, z);
		}
		else {
			printf("%lld\n", query(x, y));
		}
	}
	return 0;
}