- 【模板】前缀和
int main()
{
int n, q;
cin >> n >> q;
vector<long long> v(n+1, 0);
for(int i = 1; i <= n; ++i)
{
cin >> v[i];
v[i] += v[i-1];
}
int l, r;
while(cin >> l >> r)
{
cout << v[r] - v[l - 1] << endl;
}
return 0;
}
- 【模板】二维前缀和
int main()
{
int n, m, q; // n 行, m 列
cin >> n >> m >> q;
vector<vector<long long>> vv(n+1, vector<long long>(m+1, 0));
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
cin >> vv[i][j];
vv[i][j] += (vv[i - 1][j] + vv[i][j - 1] - vv[i - 1][j - 1]);
}
}
int x1, y1, x2, y2;
while(cin >> x1 >> y1 >> x2 >> y2)
{
cout << vv[x2][y2] - vv[x1-1][y2] - vv[x2][y1-1] + vv[x1-1][y1-1] << endl;
}
return 0;
}
- 寻找数组的中心下标
int pivotIndex(vector<int>& nums)
{
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
for(int i = 1; i < n; ++i)
{
dp[i] = nums[i] + dp[i-1];
}
if(dp[n-1] - dp[0] == 0) return 0;
for(int i = 1; i < n; ++i)
{
if(dp[i-1] == dp[n-1] - dp[i]) return i;
}
return -1;
}
- 除自身以外数组的乘积
// 空间复杂度 - O(n)
vector<int> productExceptSelf(vector<int>& nums)
{
int n = nums.size();
// f[i] - 表示 [0, i-1] 区间元素的乘积 -> f[i] = f[i-1] * nums[i-1];
vector<int> f(n);
// g[i] - 表示 [i+1, n-1] 区间元素的乘积 -> g[i] = g[i+1] * nums[i+1];
vector<int> g(n);
f[0] = 1;
g[n-1] = 1;
for(int i = 1; i < n; ++i)
{
f[i] = f[i-1] * nums[i-1];
}
for(int i = n-2; i >= 0; --i)
{
g[i] = g[i+1] * nums[i+1];
}
vector<int> ret(n);
for(int i = 0; i < n; ++i)
{
ret[i] = f[i] * g[i];
}
return ret;
}
// 空间复杂度 - O(1)
vector<int> productExceptSelf(vector<int>& nums)
{
int n = nums.size();
vector<int> dp(n);
dp[0] = nums[0];
for(int i = 1; i < n; ++i)
{
dp[i] = nums[i] * dp[i-1];
}
int right = 1;
for(int i = n-1; i >= 1; --i)
{
dp[i] = dp[i-1] * right;
right *= nums[i];
}
dp[0] = right;
return dp;
}
- 和为 K 的子数组
unordered_map<int, int> hash; // <前缀和, 次数>
int subarraySum(vector<int>& nums, int k)
{
hash[0] = 1;
int sum = 0, ret = 0;
for(int e : nums)
{
sum += e; // 计算当前位置的前缀和
if(hash.count(sum - k)) ret += hash[sum - k];
hash[sum]++;
}
return ret;
}
- 和可被 K 整除的子数组
// 1.同余定理: 如果 (a - b) / p = k ... 0 则推出 a % p = b % p
// 2.因为 负 % 正 = 负, 所以为兼顾取模结果的正负性, 使用 (a % p + p) % p 做修正
unordered_map<int, int> hash; // <前缀和sum的余数, 次数>
int subarraysDivByK(vector<int>& nums, int k)
{
hash[0] = 1;
int sum = 0, ret = 0;
for(int e : nums)
{
sum += e;
int r = (sum % k + k) % k; // 修正后的余数
if(hash.count(r)) ret += hash[r];
hash[r]++;
}
return ret;
}
- 连续数组
// 转化:将所有的0改为-1, 转化为寻找和为0的最长子数组
unordered_map<int, int> hash; // <前缀和, 下标>
int findMaxLength(vector<int>& nums)
{
for(int& e : nums) if(e == 0) e = -1;
hash[0] = -1;
int sum = 0, len = 0;
for(int i = 0; i < nums.size(); ++i)
{
sum += nums[i];
if(hash.count(sum)) len = max(len, i - hash[sum]);
else hash[sum] = i;
}
return len;
}
- 矩阵区域和
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
{
int m = mat.size(), n = mat[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1));
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
}
}
vector<vector<int>> answer(m, vector<int>(n));
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
// 左上角 - [i-k, j-k]
// 右下角 - [i+k, j+k]
int top = max(0, i-k) + 1, left = max(0, j-k) + 1;
int bottom = min(m-1, i+k) + 1, right = min(n-1, j+k) + 1;
answer[i][j] = dp[bottom][right] - dp[bottom][left-1] - dp[top-1][right] + dp[top-1][left-1];
}
}
return answer;
}