这是一段关于二维线段树的代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4040;
#define int long long
int tree[maxn][maxn], lazy[maxn][maxn];
int n, q;
void push_up (int rtx, int rty) {
tree[rtx][rty] = tree[rtx << 1][rty << 1] + tree[rtx << 1][rty << 1 | 1] + tree[rtx << 1 | 1][rty << 1] + tree[rtx << 1 | 1][rty << 1 | 1];
}
void push_down (int xl, int xr, int yl, int yr, int rtx, int rty) {
if ((xl != xr || yl != yr) && lazy[rtx][rty]) {
int midx = (xl + xr) >> 1;
int midy = (yl + yr) >> 1;
tree[rtx << 1][rty << 1] += lazy[rtx][rty] * (midx - xl + 1) * (midy - yl + 1);
tree[rtx << 1][rty << 1 | 1] += lazy[rtx][rty] * (midx - xl + 1) * (yr - midy);
tree[rtx << 1 | 1][rty << 1] += lazy[rtx][rty] * (xr - midx) * (midy - yl + 1);
tree[rtx << 1 | 1][rty << 1 | 1] += lazy[rtx][rty] * (xr - midx) * (yr - midy);
lazy[rtx << 1][rty << 1] += lazy[rtx][rty];
lazy[rtx << 1][rty << 1 | 1] += lazy[rtx][rty];
lazy[rtx << 1 | 1][rty << 1] += lazy[rtx][rty];
lazy[rtx << 1 | 1][rty << 1 | 1] += lazy[rtx][rty];
}
lazy[rtx][rty] = 0;
}
void update (int xL, int xR, int yL, int yR, int xl, int xr, int yl, int yr, int rtx, int rty, int x) {
if (xL <= xl && xr <= xR && yL <= yl && yr <= yR) {
tree[rtx][rty] += (xr - xl + 1) * (yr - yl + 1) * x;
lazy[rtx][rty] += x;
}
else {
int midx = (xl + xr) >> 1;
int midy = (yl + yr) >> 1;
if (xL <= midx && yL <= midy) update (xL, xR, yL, yR, xl, midx, yl, midy, rtx << 1, rty << 1, x);
if (xL <= midx && midy < yR) update (xL, xR, yL, yR, xl, midx, midy + 1, yr, rtx << 1, rty << 1 | 1, x);
if (midx < xR && yL <= midy) update (xL, xR, yL, yR, midx + 1, xr, yl, midy, rtx << 1 | 1, rty << 1, x);
if (midx < xR && midy < yR) update (xL, xR, yL, yR, midx + 1, xr, midy + 1, yr, rtx << 1 | 1, rty << 1 | 1, x);
push_up (rtx, rty);
}
}
int query (int xL, int xR, int yL, int yR, int xl, int xr, int yl, int yr, int rtx, int rty) {
if (xL <= xl && xr <= xR && yL <= yl && yr <= yR) return tree[rtx][rty];
push_down (xl, xr, yl, yr, rtx, rty);
int ans = 0;
int midx = (xl + xr) >> 1;
int midy = (yl + yr) >> 1;
if (xL <= midx && yL <= midy) ans += query (xL, xR, yL, yR, xl, midx, yl, midy, rtx << 1, rty << 1);
if (xL <= midx && midy < yR) ans += query (xL, xR, yL, yR, xl, midx, midy + 1, yr, rtx << 1, rty << 1 | 1);
if (midx < xR && yL <= midy) ans += query (xL, xR, yL, yR, midx + 1, xr, yl, midy, rtx << 1 | 1, rty << 1);
if (midx < xR && midy < yR) ans += query (xL, xR, yL, yR, midx + 1, xr, midy + 1, yr, rtx << 1 | 1, rty << 1 | 1);
return ans;
}
signed main () {
cin >> n >> q;
while (q--) {
string s;
cin >> s;
if (s == string ("addpoint")) {
int x, y, num;
cin >> x >> y >> num;
update (x, x, y, y, 1, n, 1, n, 1, 1, num);
}
if (s == string ("addarea")) {
int xl, xr, yl, yr, num;
cin >> xl >> yl >> xr >> yr >> num;
update (xl, xr, yl, yr, 1, n, 1, n, 1, 1, num);
}
if (s == string ("querypoint")) {
int x, y;
cin >> x >> y;
cout << query (x, x, y, y, 1, n, 1, n, 1, 1) << endl;
}
if (s == string ("queryareasum")) {
int xl, xr, yl, yr;
cin >> xl >> yl >> xr >> yr;
cout << query (xl, xr, yl, yr, 1, n, 1, n, 1, 1) << endl;
}
}
return 0;
}
样例输入
4 5
addpoint 2 2 5
addarea 1 2 3 4 6
querypoint 2 2
addpoint 2 3 7
queryareasum 1 1 4 4
样例输出
11
66
有谁帮我指出一下问题吗,万分感谢!