目录

1前缀和 

1.1一维前缀和

1.2二维前缀和

2.题目

2.1输入描述:

2.2输出描述:

2.3输入

2.4输出

3.题目理解 

3.1思路

4.程序

4.1运行结果

 1前缀和 

1.1一维前缀和

1.2二维前缀和

求D=（A+B+C+D）-(A+B)-(A+C)+A

D=a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]

a[][]这里代表的是二维前缀和

  

   

    

     

    
    

     

      for(int i=1;i<=n;i++){
     
    
   

    

     

    
    

     
	for(int j=1;j<=m;j++)
     
    
   

    

     

    
    

     

      	a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
     
    
   

    

     

    
    

     

      } 
     
    
  
 

假如我想求a[2][4]的前缀和，我得先加上a[1][4]的前缀和，再加上a[2][3]的前缀和，然后这个时候我们发现实际上a[1][3]这个部分我们加了两遍，所以我们需要再减去一遍a[1][3]，于是得出公式a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1]。

2.题目

一闪一闪亮晶晶，满天都是小星星，牛牛晚上闲来无聊，便躺在床上数星星。

牛牛把星星图看成一个平面，左上角为原点(坐标为(1, 1))。现在有n颗星星，他给每颗星星都标上坐标(xi，yi)，表示这颗星星在第x行，第y列。

现在，牛牛想问你m个问题，给你两个点的坐标(a1, b1)(a2，b2)，表示一个矩形的左上角的点坐标和右下角的点坐标，请问在这个矩形内有多少颗星星（边界上的点也算是矩形内）。

2.1输入描述:

第一行输入一个数字n(1≤n≤100000)，表示星星的颗数。
接下来的n行，每行输入两个数xi和yi(1≤xi，yi≤1000），表示星星的位置。
然后输入一个数字m(1≤m≤100000), 表示牛牛询问问题的个数。
接下来m行，每行输入四个数字a1，b1，a2，b2(1≤a1＜a2≤1000), (1≤b1＜b2≤1000）
题目保证两颗星星不会存在于同一个位置。

2.2输出描述:

输出一共包含m行，每行表示与之对应的每个问题的答案。

2.3输入

4
1 1
2 2
3 3
1 3
4
1 1 2 2
1 1 3 3
2 2 3 3
1 2 2 3

2.4输出

2
4
2
2

3.题目理解 

刚开始读题目的时候，我还以为是

但是阅读示例后，发现 并不是这个样子！

这个棋盘等于说是有空格地方，不是满的，我们需要对其进行统计

3.1思路

该怎么做这道题？

看了示例数据

第一行输入一个数字n(1≤n≤100000)，表示星星的颗数。

接下来的n行，每行输入两个数xi和yi(1≤xi，yi≤1000），表示星星的位置。

然后输入一个数字m(1≤m≤100000), 表示牛牛询问问题的个数。

接下来m行，每行输入四个数字a1，b1，a2，b2(1≤a1＜a2≤1000), (1≤b1＜b2≤1000）

题目保证两颗星星不会存在于同一个位置。

4.程序

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      int const N = 1000;
     
    
   

    

     

    
    

     

      int a[N][N];
     
    
   

    

     

    
    

     

      int flag[N][N];
     
    
   

    

     

    
    

     

      int ans[100010];
     
    
   

    

     

    
    

     

      int t;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int n, m, C;
     
    
   

    

     

    
    

     
	cout << "请您输入n的值：\n";
     
    
   

    

     

    
    

     
	cin >> n;
     
    
   

    

     

    
    

     
	int x1, y1, x2, y2, x, y;
     
    
   

    

     

    
    

     
	for (int i = 1; i <= n; i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		cout << "请输入x,y的值（示例 ： 5 3）" << endl;
     
    
   

    

     

    
    

     
		cin >> x >> y;
     
    
   

    

     

    
    

     

      		flag[x][y] = 1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	for (int i = 1; i < N; i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		for (int j = 1; j < N; j++)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			a[i][j] = a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1] + flag[i][j];
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	cout << "请输入m的值：" << endl;
     
    
   

    

     

    
    

     
	cin >> m;
     
    
   

    

     

    
    

     
	for (int i = 1; i <= m; i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		cout << "请输入x1,y1,x2,y2的值（示例：1 1 3 3）：" << endl;
     
    
   

    

     

    
    

     
		cin >> x1 >> y1 >> x2 >> y2;
     
    
   

    

     

    
    

     

      		C = a[x2][y2] - a[x2][y1 - 1] - a[x1 - 1][y2] + a[x1 - 1][y1 - 1];
     
    
   

    

     

    
    

     

      		ans[t++] = C;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	for (int i = 0; i < t; i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		cout << ans[i] << endl;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

4.1运行结果

参考：

前缀和、二维前缀和与差分的小总结 （讲的不错）

二维前缀和详解

文章来源: kings.blog.csdn.net，作者：人工智能博士，版权归原作者所有，如需转载，请联系作者。

原文链接：kings.blog.csdn.net/article/details/95051326