【算法一周目】从时光的边缘看世界：前缀和揭示的算法真谛

#include <iostream>
#include <vector>
using namespace std;

int main() {
    //处理输入输出
    int n, q;
    cin >> n >> q;
    vector<int> arr(n + 1);
    for(int i = 1; i <= n; ++i) cin >> arr[i];

    //预处理dp数组，long long元素类型防止溢出
    vector<long long> dp(n + 1);
    for(int i = 1; i <= n; ++i) dp[i] = dp[i - 1] + arr[i];

    int l, r;
    while(q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    //处理输入数据
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> vv(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
            cin >> vv[i][j];
    }

    //预处理矩阵数组, longlong防溢出  
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for(int i = 1; i<=n; ++i)
    {
        for(int j = 1; j <= m; ++j)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + vv[i][j] - dp[i - 1][j - 1];
    }

    //输出
    int x1, y1, x2, y2;
    while(q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        long long ret = dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1];
        cout << ret << endl;
    }

    return 0;
}

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        //预处理出前缀和、后缀和数组
        int n = nums.size();
        vector<int> f(n);
        //数组起始位置的左侧
        for(int i = 1; i < n; ++i)
            f[i] = f[i - 1] + nums[i - 1];
        
        vector<int> g(n);
        for(int i = n - 2; i >= 0; --i)
            g[i] = g[i + 1] + nums[i + 1];
        
        //遍历数组找到中心下标
        for(int i = 0; i < n; ++i)
        {    if(f[i] == g[i])
                return i;
        }
        return -1;
    }
};

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int sum = 0;
        for(auto e : nums)
            sum += e;
        
        int leftSum = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            if(2 * leftSum == sum - nums[i])
                return i;
            
            leftSum += nums[i];
        }
        return -1;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n,1);
        for(int i = 1; i < n; ++i)
            f[i] = f[i - 1] * nums[i - 1];

        vector<int> g(n,1);
        for(int i = n - 2; i >= 0; --i)
            g[i] = g[i + 1] * nums[i + 1];
        
        vector<int> ret;
        for(int i = 0; i < n; ++i)
            ret.push_back(f[i] * g[i]);
        
        return ret;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> g(n,1);
        //后缀积
        for(int i = n - 2; i >= 0; --i)
            g[i] = g[i + 1] * nums[i + 1];
        
        //遍历修改g[i]
        //pre为i位置左侧元素的乘积
        int pre = 1;
        for(int i = 0; i < n; ++i)
        {
            
            g[i] *= pre;
            pre *= nums[i];
        }
        
        return g;
    }
};

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        //哈希表记录前缀和及其出现的次数
        unordered_map<int, int> hash;
        //处理区间和为K的特殊情况
        hash[0] = 1;

        int sum = 0, ret = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            //计算[0,i]的前缀和
            sum += nums[i];
            //查找和为sum-k的子数组的个数
            if(hash.count(sum - k)) ret += hash[sum-k];
            //将前缀和加入哈希表
            hash[sum]++;
        }
        return ret;
    }
};

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        //哈希表存储前缀和余数及其出现的次数
        unordered_map<int, int> hash;
        //处理区间元素和刚好被K整除，余数为0的特殊情况
        hash[0] = 1;

        int ret = 0, sum = 0;
        for(auto e : nums)
        {
            //计算前缀和
            sum += e;
            //对前缀和取模，注意在C++中，余数可为负
            //需要换算成非负以免影响结果
            int mod = (sum % k + k) % k;
            //查找前缀和的余数为mod的子数组的个数
            if(hash.count(mod))
                ret += hash[mod];
            //将余数加入哈希表
            hash[mod]++;
        }
        return ret;
    }
};

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        //哈希表存储的是[0,i]区间元素和及其下标i
        unordered_map<int, int> hash;
        //处理前缀和刚好为0的情况
        hash[0] = -1;

        int sum = 0, ret = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            //将数组中的0看待成-1
            sum += nums[i] == 0 ? -1 : 1;
            //如果前缀和存在则更新结果，不存在再加入哈希表
            if(hash.count(sum)) ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        //1.初始化前缀和数组，需要多加一行多加一列
        int m = mat.size(), n = mat[0].size();
        //dp[i][j]代表矩阵mat从[0][0]到[i-1][j-1]的所有元素的和
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i < m + 1; ++i)
            for(int j = 1; j < n + 1; ++j)
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];
        
        //2.使用前缀和数组求和
        vector<vector<int>> ret(m, vector<int>(n));
        for(int i = 0; i < m; ++i)
        {
            //下标转换并且要进行越界情况的处理
            int x1 = max(0, i - k) + 1;
            int x2 = min(m - 1, i + k) + 1;
            for(int j = 0; j < n; ++j)
            {
                int y1 = max(0, j - k) + 1;
                int y2 = min(n - 1, j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            }
        }
        return ret;
    }
};