天上的星星（二维前缀和）

本文主要是介绍天上的星星（二维前缀和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在一个星光摧残的夜晚，蒜头君一颗一颗的数这天上的星星。

蒜头君给在天上巧妙的画了一个直角坐标系，让所有的星星都分布在第一象。天上有

现在，蒜头君问自己

输入格式

第一行输入一个整数 $\le n \le 50000)n(1≤n≤50000) 表示星星的数量。$

接下里 $\le x, y, w\le 2000)x,y,w(0≤x,y,w≤2000)，表示在坐标 (x,y)(x,y) 有一颗亮度为 ww 的星星。注意一个点可能有多个星星。$

接下来一行输入一个整数 $\le q \le 50000)q(1≤q≤50000)，表示查询的次数。$

接下来 $x_1, y_1, x_2, y_2x1,y1,x2,y2，其中 (x_1, y_1)(x1,y1) 表示查询的矩形的左下角的坐标，(x_2, y_2)(x2,y2) 表示查询的矩形的右上角的坐标，0 \le x_1 \le x_2 \le 20000≤x1≤x2≤2000，0 \le y_1 \le y_2 \le 20000≤y1≤y2≤2000。$

输出格式

对于每一次查询，输出一行一个整数，表示查询的矩形区域内的星星的亮度总和。

样例输入复制

样例输出复制

思路：

这道题其实就是一个裸的二维前缀和的问题，只要前面掌握了如何去求二维前缀和那么这道题就不会有问题了。

然后要注意我们比较的点是 (1,1)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <stdlib.h>
 4 #include <string>
 5 #include <string.h>
 6 #include <set>
 7 #include <queue>
 8 #include <stdbool.h>
 9 
10 #define LL long long
11 using namespace std;
12 const int MAXN=2005;
13 
14 int map[MAXN][MAXN];
15 int dp[MAXN][MAXN];
16 
17 int main()
18 {
19 #ifndef ONLINE_JUDGE
20     freopen("../in.txt","r",stdin);
21 #endif
22     int n,x,y,w;
23     scanf("%d",&n);
24     memset(dp,0, sizeof(dp));
25     for (int i=0;i<n;i++)
26     {
27         cin >> x >> y >> w;
28         map[++x][++y] += w;
29     }
30     for (int i=1;i<=2001;i++)
31     {
32         for (int j=1;j<=2001;j++)
33         {
34             dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+map[i][j];
35         }
36     }
37     scanf("%d",&n);
38     while (n--)
39     {
40         int x1,y1,x2,y2 ;
41         scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
42         x1++ ;
43         y1++ ;
44         x2++ ;
45         y2++ ;
46         cout <<(dp[x2][y2]+dp[x1-1][y1-1]-dp[x1-1][y2]-dp[x2][y1-1])<<endl;
47     }
48 }