本文主要是介绍计蒜客-天上的星星（二维前缀和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
天上的星星
在一个星光摧残的夜晚，蒜头君一颗一颗的数这天上的星星。
蒜头君给在天上巧妙的画了一个直角坐标系，让所有的星星都分布在第一象。天上有 nnn 颗星星，他能知道每一颗星星的坐标和亮度。
现在，蒜头君问自己 qqq 次，每次他问自己每个矩形区域的星星的亮度和是多少（包含边界上的星星）。
输入格式
第一行输入一个整数 n(1≤n≤50000)n(1 \le n \le 50000)n(1≤n≤50000) 表示星星的数量。
接下里 nnn 行，每行输入三个整数 x,y,w(0≤x,y,w≤2000)x,y,w(0 \le x, y, w\le 2000)x,y,w(0≤x,y,w≤2000)，表示在坐标 (x,y)(x,y)(x,y) 有一颗亮度为 www 的星星。注意一个点可能有多个星星。
接下来一行输入一个整数 q(1≤q≤50000)q(1 \le q \le 50000)q(1≤q≤50000)，表示查询的次数。
接下来 qqq 行，每行输入四个整数 x1,y1,x2,y2x_1, y_1, x_2, y_2x1,y1,x2,y2，其中 (x1,y1)(x_1, y_1)(x1,y1) 表示查询的矩形的左下角的坐标，(x2,y2)(x_2, y_2)(x2,y2) 表示查询的矩形的右上角的坐标，0≤x1≤x2≤20000 \le x_1 \le x_2 \le 20000≤x1≤x2≤2000，0≤y1≤y2≤20000 \le y_1 \le y_2 \le 20000≤y1≤y2≤2000。
输出格式
对于每一次查询，输出一行一个整数，表示查询的矩形区域内的星星的亮度总和。
样例输入
5 5 0 6 7 9 7 8 6 13 9 7 1 3 0 19 4 0 8 7 9 0 0 7 10 2 7 10 9 5 4 7 5
样例输出
7 32 8 0
二维前缀和
需要注意的是他给的是在坐标轴中的坐标，横轴x轴，纵轴y轴，而我们在二维数组中统计的时候是吧每行当x，每列当y
所以题目查询时所给的左下角和右上角，在二维数组矩阵中恰好就对应了矩阵中的左上角和右下角（顺时针旋转了90°）
code：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 2010;
ll mp[maxn][maxn],sum[maxn][maxn];int main(){int n,x,y;ll w;cin >> n;while(n--){cin >> x >> y >> w;mp[x+1][y+1] += w;}for(int i = 1; i < maxn; i++){for(int j = 1; j < maxn; j++){sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mp[i][j];}}int q;cin >> q;while(q--){int x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;x1++,y1++,x2++,y2++;cout << sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1] << endl;}return 0;
}
这篇关于计蒜客-天上的星星（二维前缀和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
