二维树状数组,这两写法有什么区别嘛??答案不同
  • 板块学术版
  • 楼主_Goodnight
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/11/28 16:41
  • 上次更新2023/11/3 23:20:53
查看原帖
二维树状数组,这两写法有什么区别嘛??答案不同
448910
_Goodnight楼主2021/11/28 16:41

对于单点修改,区间查询,第一个是正解的

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
ll t[4099][4099];
void add(int x, int y, int w) {
    for (; x <= n; x += x & -x)
        for (int z = y; z <= m; z += z & -z)
            t[x][z] += w;
}
ll sum(int x, int y, ll r = 0) {
    for (; x; x -= x & -x)
        for (int z = y; z; z -= z & -z)
            r += t[x][z];

    return r;
}
int main() {
    int o, a, b, c, d;
    scanf("%d%d", &n, &m);

    while (~scanf("%d%d%d%d", &o, &a, &b, &c))
        if (o == 1)
            add(a, b, c);
        else
            scanf("%d", &d), printf("%lld\n", sum(c, d) - sum(a - 1, d) - sum(c, b - 1) + sum(a - 1, b - 1));

    return 0;
}

第二个是我自己写的

#include<bits/stdc++.h>
using namespace std;
#define INF 2000000000
#define lowbit(x) (x&(-x))
typedef  long long ll;
const int maxn = 4200;
int n, m, c[maxn][maxn];
void add(int x, int y,int k) {
	int i = x, j = y;
	while (i <= n) {
		while (j <= m) {
			c[i][j] += k; j += lowbit(j);
		}
		i += lowbit(i);
	}
}
ll sum(int x, int y) {
	ll ans = 0;
	int i = x, j = y;
	while (i > 0) {
		while (j > 0) {
			ans += c[i][j], j -= lowbit(j);
		}
		i -= lowbit(i);
	}
	return ans;
}
int main() {
	cin >> n >> m;
	int opt, x, y, k, a, b, c, d;
	while (cin>>opt) {
		if (opt == 1) {
			cin >> x >> y >> k;
			add(x, y, k);
		}
		else {
			cin >> a >> b >> c >> d;
			cout << sum(c, d)-sum(c,b-1)-sum(a-1,d)+sum(a-1,b-1)<<endl;
		}
	}
}

第一个能A,而第二个不能,这是为什么呢

2021/11/28 16:41
加载中...