Java教程

前缀和 算法总结

本文主要是介绍前缀和 算法总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一维前缀和

 

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<math.h>
 5 using namespace std;
 6 int a[1000010], s[1000010], m, n;
 7 int main()
 8 {
 9     s[0] = 0;
10     cin >> n >> m;
11     for (int i = 1; i <= n; i++)
12     {
13         cin >> a[i];
14         s[i] = s[i - 1] + a[i];
15     }
16     while (m--)
17     {
18         int l, r;
19         cin >> l >> r;
20         cout << s[r] - s[l - 1] << endl;
21     }
22     return 0;
23 }
View Code

 

 

二维前缀和

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

 

 int x1, y1, x2, y2;
 cin >> x1 >> y1 >> x2 >> y2;
 cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] +  s[x1-1][y1-1] << endl;

 

 

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cmath>
 4 #include<math.h>
 5 using namespace std;
 6 int a[1010][1010], s[1010][1010], m, n,q;
 7 int main()
 8 {
 9     s[0][0] = 0;
10     cin >> n >> m >> q;
11     for (int i = 1; i <= n; i++)
12     {
13         for (int j = 1; j <= m; j++)
14         {
15             cin >> a[i][j];
16             s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i-1][j-1];
17         }
18     }
19     while (q--)
20     {
21         int x1, y1, x2, y2;
22         cin >> x1 >> y1 >> x2 >> y2;
23         cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] +  s[x1-1][y1-1] << endl;
24 
25     }
26   
27     return 0;
28 }
View Code

 

这篇关于前缀和 算法总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航