前缀和与差分
一维前缀和
a[i] 表示数组中第i个数、s[i]表示为前i个数之和
s[i] = a[1] + a[2] + ……+ a[i] = s[i-1] + a[i][l, r]区间内数的和：s[r] - s[l-1]（为了当l=1时不需要进行特判。规定s[0]记为0，且读入数组的时候从下标1开始记录）
1 | S[i] = a[1] + a[2] + ... a[i] |
封装一下1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25// 一维前缀和
class PreSum {
public:
PreSum(vector<int>& nums);
/* 查询闭区间 [left, right] 的累加和 */
int query(int left, int right);
private:
vector<int> m_preSum;
};
PreSum::PreSum(vector<int>& nums)
{
int n = nums.size();
m_preSum.resize(n + 1);
for (int i = 1; i < n + 1; i++)
{
m_preSum[i] = m_preSum[i - 1] + nums[i - 1];
}
}
int PreSum::query(int left, int right)
{
return m_preSum[right + 1] - m_preSum[left];
}
一维差分
差分是前缀和的逆运算，简单封装1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40class Difference
{
public:
Difference(vector<int> nums);
void increment(int i, int j, int val);
vector<int> result();
private:
vector<int> m_diff;
};
Difference::Difference(vector<int> nums)
{
int size = nums.size();
m_diff.resize(size);
for (int i = 1; i < size; i++)
{
m_diff[i] = nums[i] - nums[i - 1];
}
}
void Difference::increment(int i, int j, int val)
{
m_diff[i] += val;
if (j + 1 < m_diff.size()) {
m_diff[j + 1] -= val;
}
}
vector<int> Difference::result()
{
vector<int> res(m_diff.size());
res[0] = m_diff[0];
for (int i = 1; i < m_diff.size(); i++) {
res[i] = res[i - 1] + m_diff[i];
}
return res;
}