网站建设推介会发言稿,在线网站做成app,网站建设力度,php网站开发外文前缀和作用#xff1a;
快速求出原数组中一段数组的和
思路
1.预处理前缀和数组
2.用公式求区间和
公式#xff1a; 二维前缀和#xff1a; s [ i ] [ j ] s[ i - 1 ] [ j ] s[ i ] [ j - 1 ] - s [ i - 1 ] [ j - 1]; 题型 一维 二维 题解 一维 #include iost…前缀和作用
快速求出原数组中一段数组的和
思路
1.预处理前缀和数组
2.用公式求区间和
公式 二维前缀和 s [ i ] [ j ] s[ i - 1 ] [ j ] s[ i ] [ j - 1 ] - s [ i - 1 ] [ j - 1]; 题型 一维 二维 题解 一维 #include iostreamusing namespace std;const int N 100010;int n, m;
int a[N], s[N];int main()
{scanf(%d%d, n, m);for (int i 1; i n; i ) scanf(%d, a[i]);for (int i 1; i n; i ) s[i] s[i - 1] a[i]; // 前缀和的初始化while (m -- ){int l, r;scanf(%d%d, l, r);printf(%d\n, s[r] - s[l - 1]); // 区间和的计算}return 0;
}二维 #include iostreamusing namespace std;const int N 1010;int n, m, q;
int s[N][N];int main()
{scanf(%d%d%d, n, m, q);for (int i 1; i n; i )for (int j 1; j m; j )scanf(%d, s[i][j]);for (int i 1; i n; i )for (int j 1; j m; j )s[i][j] s[i - 1][j] s[i][j - 1] - s[i - 1][j - 1];while (q -- ){int x1, y1, x2, y2;scanf(%d%d%d%d, x1, y1, x2, y2);printf(%d\n, s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] s[x1 - 1][y1 - 1]);}return 0;
}
