树状数组的扩展

标签：typedef ch limits 树状 sum 扩展 long 数组 include

二维区间 修改+查询

例题

题目是求 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m a_{i,j}\) 我们可以定义一个差分数组 \(d_{i,j}=a_{i,j}+a_{i-1,j-1}-a_{i-1,j}-a_{i,j-1}\) 易知 \(a_{i,j}=\sum\limits_{x=1}^{i}\sum\limits_{y=1}^j d_{x,y}\)

接着我们可以利用差分来简化题意，我们只需要求出 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^m a_{i,j}\) 就行了。

\[\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^m a_{i,j}&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{k=1}^i\sum\limits_{l=1}^j d_{k,l}\\&=\sum\limits_{i=1}^n\sum\limits_{j=1}^m d_{i,j}(n-i+1)(m-j+1)\\&=(n+1)(m+1)\sum\limits_{i=1}^n\sum\limits_{j=1}^m d_{i,j}-(m+1)\sum\limits_{i=1}^n\sum\limits_{j=1}^md_{i,j}\times i - (n+1)\sum\limits_{i=1}^n\sum\limits_{j=1}^md_{i,j}\times j+\sum\limits_{i=1}^n\sum\limits_{j=1}^m d_{i,j}\times i \times j\end{aligned} \]

用 \(4\) 个二维树状数组进行处理就可以了。

时间复杂度\(O(\log_2n\log_2m )\) 缺点是空间占用太多。

代码：

#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define endl '\n'
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
typedef pair<ll, ll> pll;

inline ll read() {
	char ch = getchar(); ll fu = 0, s = 0;
	while(!isdigit(ch)) fu |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	return fu ? -s : s;
}

const int MAXN = 2050;
struct Node {
	int d1, d2, d3, d4;
} tree[MAXN][MAXN];
int n, m; char op[2];
#define lowbit(x) ((x) & -(x))

void update(int x, int y, int d) {
	for (int i = x; i <= n; i += lowbit(i)) {
		for (int j = y; j <= m; j += lowbit(j)) {
			tree[i][j].d1 += d;
			tree[i][j].d2 += x * d;
			tree[i][j].d3 += y * d;
			tree[i][j].d4 += x * y * d;
		}
	}
}

int sum(int x, int y) {
	int ans = 0;
	for (int i = x; i; i -= lowbit(i)) {
		for (int j = y; j; j -= lowbit(j)) {
			ans += (x + 1) * (y + 1) * tree[i][j].d1 - (y + 1) * tree[i][j].d2 - (x + 1) * tree[i][j].d3 + tree[i][j].d4;
		}
	}
	return ans;
}

void solve() {
	scanf("%s", op);
	n = read(), m = read();
	while (scanf("%s", op) != -1) {
		int x1 = read(), y1 = read(), x2 = read(), y2 = read();
		if (op[0] == 'L') {
			int d = read();
			update(x1, y1, d), update(x2 + 1, y2 + 1, d);
			update(x1, y2 + 1, -d), update(x2 + 1, y1, -d);
		} else {
			printf("%d\n", sum(x2, y2) + sum(x1 - 1, y1 - 1) - sum(x1 - 1, y2) - sum(x2, y1 - 1));
		}
	}
}

signed main() {
	int T = 1;
	// T = read();
	while(T--) solve();
	return 0;
}

标签：typedef,ch,limits,树状,sum,扩展,long,数组,include
From： https://www.cnblogs.com/wh2011/p/18650915