茶叶网站设计,大学 网站开发 专业,中国核工业二三建设有限公司招聘信息,做网站找那些公司1 前缀和
一维前缀和是指对于一个数组 a a a#xff0c;我们定义一个新的数组 s s s#xff0c;其中每个元素 s [ i ] s[i] s[i] 表示从数组开头到第 i i i 个元素的累加和#xff1a; s [ i ] a [ 1 ] a [ 2 ] ⋯ a [ i ] ∑ j 1 i a [ j ] s[i] a[1] a[2] \…1 前缀和
一维前缀和是指对于一个数组 a a a我们定义一个新的数组 s s s其中每个元素 s [ i ] s[i] s[i] 表示从数组开头到第 i i i 个元素的累加和 s [ i ] a [ 1 ] a [ 2 ] ⋯ a [ i ] ∑ j 1 i a [ j ] s[i] a[1] a[2] \cdots a[i] \sum_{j1}^{i} a[j] s[i]a[1]a[2]⋯a[i]j1∑ia[j]
通过预处理前缀和数组 s s s我们可以快速计算任意区间 [ l , r ] [l, r] [l,r] 的和 sum ( l , r ) s [ r ] − s [ l − 1 ] \text{sum}(l, r) s[r] - s[l - 1] sum(l,r)s[r]−s[l−1]
如果 l 1 l 1 l1则 sum ( l , r ) s [ r ] \text{sum}(l, r) s[r] sum(l,r)s[r]。
二维前缀和是前缀和思想的扩展适用于矩阵。对于一个 n × m n \times m n×m 的矩阵 a a a我们定义一个二维前缀和矩阵 s s s其中 s [ i ] [ j ] s[i][j] s[i][j] 表示从矩阵左上角 ( 1 , 1 ) (1, 1) (1,1) 到右下角 ( i , j ) (i, j) (i,j) 的所有元素的和 s [ i ] [ j ] ∑ x 1 i ∑ y 1 j a [ x ] [ y ] s[i][j] \sum_{x1}^{i} \sum_{y1}^{j} a[x][y] s[i][j]x1∑iy1∑ja[x][y]
通过二维前缀和矩阵 s s s我们可以快速计算任意子矩阵 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) 到 ( x 2 , y 2 ) (x_2, y_2) (x2,y2) 的和 s ( x 1 , y 1 , x 2 , y 2 ) s [ x 2 ] [ y 2 ] − s [ x 1 − 1 ] [ y 2 ] − s [ x 2 ] [ y 1 − 1 ] s [ x 1 − 1 ] [ y 1 − 1 ] {s}(x_1, y_1, x_2, y_2) s[x_2][y_2] - s[x_1-1][y_2] - s[x_2][y_1-1] s[x_1-1][y_1-1] s(x1,y1,x2,y2)s[x2][y2]−s[x1−1][y2]−s[x2][y1−1]s[x1−1][y1−1] 2 一维板子
原题链接DP34 【模板】前缀和
给定一个长度为 n n n 的数组 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an。接下来有 q q q 次查询每次查询有两个参数 l , r l, r l,r。对于每个询问请输出 a l a l 1 . . . a r a_l a_{l1} ... a_r alal1...ar。
输入描述
第一行包含两个整数 n n n 和 q q q第二行包含 n n n 个整数表示 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an。接下来 q q q 行每行包含两个整数 l l l 和 r r r。 1 ≤ n , q ≤ 1 0 5 1 \leq n, q \leq 10^5 1≤n,q≤105 − 1 0 9 ≤ a [ i ] ≤ 1 0 9 -10^9 \leq a[i] \leq 10^9 −109≤a[i]≤109 1 ≤ l ≤ r ≤ n 1 \leq l \leq r \leq n 1≤l≤r≤n
输出描述 输出 q q q 行每行代表一次查询的结果。
示例 input:
3 2
1 2 4
1 2
2 3output:
3
6#include iostream
#include vector
using namespace std;#define endl \n
#define LL long longvectorLL a(101010, 0);
vectorLL s(101010, 0);int main()
{int n, q;cin n q;for (int i 1; i n; i) {cin a[i];s[i] s[i - 1] a[i];}while (q--) {int l, r;cin l r;cout s[r] - s[l - 1] endl;}return 0;
}
时间复杂度 预处理前缀和数组的时间复杂度为 O ( n ) O(n) O(n)每次查询的时间复杂度为 O ( 1 ) O(1) O(1) 3 二维板子
原题链接DP35 【模板】二维前缀和
给你一个 n n n 行 m m m 列的矩阵 A A A下标从1开始。接下来有 q q q 次查询每次查询输入4个参数 x 1 x_1 x1, y 1 y_1 y1, x 2 x_2 x2, y 2 y_2 y2。请输出以 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) 为左上角 ( x 2 , y 2 ) (x_2, y_2) (x2,y2) 为右下角的子矩阵的和。
输入描述: 第一行包含三个整数 n n n, m m m, q q q。
接下来 n n n 行每行 m m m 个整数代表矩阵的元素。
接下来 q q q 行每行4个整数 x 1 x_1 x1, y 1 y_1 y1, x 2 x_2 x2, y 2 y_2 y2分别代表这次查询的参数。 1 ≤ n , m ≤ 1000 1 \leq n, m \leq 1000 1≤n,m≤1000 1 ≤ q ≤ 1 0 5 1 \leq q \leq 10^5 1≤q≤105 − 1 0 9 ≤ a [ i ] [ j ] ≤ 1 0 9 -10^9 \leq a[i][j] \leq 10^9 −109≤a[i][j]≤109 1 ≤ x 1 ≤ x 2 ≤ n 1 \leq x_1 \leq x_2 \leq n 1≤x1≤x2≤n 1 ≤ y 1 ≤ y 2 ≤ m 1 \leq y_1 \leq y_2 \leq m 1≤y1≤y2≤m
输出描述: 输出 q q q 行每行表示查询结果。
示例
输入
3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3输出
12
26#include iostreamusing namespace std;long long a[1010][1010];
long long s[1010][1010];int main()
{int n, m, q;cin n m q;for (int i 1; i n; i) {for (int j 1; j m; j) {cin a[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] a[i][j];}}int x1, x2, y1, y2;while (q--) {cin x1 y1 x2 y2;cout s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] s[x1 - 1][y1 - 1] endl;}return 0;
}习题1724.寻找数组中心下标 - e
724.寻找数组的中心下标 - easy
#include iostream
#include vector
using namespace std;/*
https://leetcode.cn/problems/find-pivot-index/description/
正常思路应该是
2 * left_sum sumclass Solution {
public:int pivotIndex(vectorint nums) {int sum reduce(nums.begin(), nums.end());int left 0;for (int i 0; i nums.size(); i) {if (2 * left sum - nums[i]) {return i;}left nums[i];}return -1;}
};*/class Solution {
public:int pivotIndex(vectorint nums){int n nums.size();if (n 0)return -1;// 前缀和数组dp1[i] 表示 nums[0] 到 nums[i-1] 的和vectorint dp1(n 1, 0); // 后缀和数组dp2[i] 表示 nums[i1] 到 nums[n-1] 的和vectorint dp2(n 1, 0); for (int i 1; i n; i) {dp1[i] dp1[i - 1] nums[i - 1];}for (int i n - 1; i 0; --i) {dp2[i] dp2[i 1] nums[i];}for (int i 0; i n; i) {if (dp1[i] dp2[i 1]) {return i;}}return -1;}
};int main()
{vectorint nums { 1, 7, 3, 6, 5, 6 };Solution sol;int ans sol.pivotIndex(nums);cout ans endl;
}习题2303.区域和检索数组不可变 - e
303. 区域和检索 - 数组不可变 - easy
// https://leetcode.cn/problems/range-sum-query-immutable/
#include iostream
#include vector
using namespace std;
class NumArray {vectorint s;
public:NumArray(vectorint nums){s.resize(nums.size() 1);for (int i 0; i nums.size(); i) {s[i 1] s[i] nums[i];}}int sumRange(int left, int right){return s[right 1] - s[left];}
};习题3238.除自身以外数组的乘积 - m
238. 除自身以外数组的乘积 - m
/* https://leetcode.cn/problems/product-of-array-except-self/description/ */#include iostream
#include vector
using namespace std;
class Solution {
public:vectorint productExceptSelf(vectorint nums){int n nums.size();vectorint ans(n, 1);for (int i 1; i n; i)ans[i] ans[i - 1] * nums[i - 1];int suffix 1;for (int i n - 1; i 0; i--) {ans[i] ans[i] * suffix;suffix * nums[i];}return ans;}
};int main()
{vectorint nums1 { 1, 2, 3, 4 };Solution sol;vectorint result1 sol.productExceptSelf(nums1);for (int num : result1) {cout num ;}cout endl;
}/*class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint pre(n, 1);for (int i 1; i n; i) {pre[i] pre[i - 1] * nums[i - 1];}vectorint suf(n, 1);for (int i n - 2; i 0; i--) {suf[i] suf[i 1] * nums[i 1];}vectorint ans(n);for (int i 0; i n; i) {ans[i] pre[i] * suf[i];}return ans;}
};*/习题4
