对于单点修改,区间查询,第一个是正解的
#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,而第二个不能,这是为什么呢