前缀和相关题目记录（未完待续...）

1 前缀和

一维前缀和是指对于一个数组 $a$，我们定义一个新的数组 $s$，其中每个元素 $s[i]$ 表示从数组开头到第 $i$ 个元素的累加和：

$$s[i]=a[1]+a[2]+\cdots +a[i]=\sum _{j=1}^{i}a[j]$$

通过预处理前缀和数组 $s$，我们可以快速计算任意区间 $[l,r]$ 的和：

$$\text{sum}(l,r)=s[r]-s[l-1]$$

如果 $l=1$，则 $\text{sum}(l,r)=s[r]$。

二维前缀和是前缀和思想的扩展，适用于矩阵。对于一个 $n\times m$ 的矩阵 $a$，我们定义一个二维前缀和矩阵 $s$，其中 $s[i][j]$ 表示从矩阵左上角 $(1,1)$ 到右下角 $(i,j)$ 的所有元素的和：
$$s[i][j]=\sum _{x=1}^i\sum _{y=1}^{j}a[x][y]$$

通过二维前缀和矩阵 $s$，我们可以快速计算任意子矩阵 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的和：
$$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]$$

---

2 一维板子

原题链接：DP34 【模板】前缀和

给定一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$。接下来有 $q$ 次查询，每次查询有两个参数 $l,r$。对于每个询问，请输出 $a_l+a_{l+1}+...+a_r$。

输入描述：

第一行包含两个整数 $n$ 和$q$，第二行包含 $n$ 个整数，表示 $a_1,a_2,...,a_n$。接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$。

• $1\le n,q\le 10^5$
• $-10^9\le a[i]\le 10^9$
• $1\le l\le r\le n$

输出描述：
输出 $q$ 行，每行代表一次查询的结果。

示例：
input:

3 2
1 2 4
1 2
2 3

output:

3
6

#include <iostream>
#include <vector>
using namespace std;#define endl '\n'
#define LL long longvector<LL> a(101010, 0);
vector<LL> 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(1)$

---

3 二维板子

原题链接：DP35 【模板】二维前缀和

给你一个 $n$ 行 $m$ 列的矩阵 $A$，下标从1开始。接下来有 $q$ 次查询，每次查询输入4个参数 $x_1$, $y_1$, $x_2$, $y_2$。请输出以 $(x_1,y_1)$ 为左上角，$(x_2,y_2)$ 为右下角的子矩阵的和。

输入描述:
第一行包含三个整数 $n$, $m$, $q$。

接下来 $n$ 行，每行 $m$ 个整数，代表矩阵的元素。

接下来 $q$ 行，每行4个整数 $x_1$, $y_1$, $x_2$, $y_2$，分别代表这次查询的参数。

• $1\le n,m\le 1000$
• $1\le q\le 10^5$
• $-10^9\le a[i][j]\le 10^9$
• $1\le x_1\le x_2\le n$
• $1\le y_1\le y_2\le m$

输出描述:
输出 $q$ 行，每行表示查询结果。

示例

输入：

3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3

输出：

12
26

#include <iostream>using 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;
}

---

习题1：724.寻找数组中心下标 - 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(vector<int>& 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(vector<int>& nums){int n = nums.size();if (n == 0)return -1;// 前缀和数组，dp1[i] 表示 nums[0] 到 nums[i-1] 的和vector<int> dp1(n + 1, 0); // 后缀和数组，dp2[i] 表示 nums[i+1] 到 nums[n-1] 的和vector<int> 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()
{vector<int> nums = { 1, 7, 3, 6, 5, 6 };Solution sol;int ans = sol.pivotIndex(nums);cout << ans << endl;
}

---

习题2：303.区域和检索数组不可变 - e

303. 区域和检索 - 数组不可变 - easy

// https://leetcode.cn/problems/range-sum-query-immutable/
#include <iostream>
#include <vector>
using namespace std;
class NumArray {vector<int> s;
public:NumArray(vector<int>& 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];}
};

---

习题3：238.除自身以外数组的乘积 - m

238. 除自身以外数组的乘积 - m

/* https://leetcode.cn/problems/product-of-array-except-self/description/ */#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums){int n = nums.size();vector<int> 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()
{vector<int> nums1 = { 1, 2, 3, 4 };Solution sol;vector<int> result1 = sol.productExceptSelf(nums1);for (int num : result1) {cout << num << " ";}cout << endl;
}/*class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> pre(n, 1);for (int i = 1; i < n; i++) {pre[i] = pre[i - 1] * nums[i - 1];}vector<int> suf(n, 1);for (int i = n - 2; i >= 0; i--) {suf[i] = suf[i + 1] * nums[i + 1];}vector<int> ans(n);for (int i = 0; i < n; i++) {ans[i] = pre[i] * suf[i];}return ans;}
};*/

---

习题4：