【前缀和】动态规划适用于高频查询的场景

• 题目描述： /LeetCode 303: Range Sum Query Immutable Matrix@Description:Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
  Implement the NumArray class:NumArray(int[] nums) Initializes the object with the integer array nums.int sumRange(int i, int j) Return the sum of the elements of the nums array in the range [i, j] inclusive (i.e., sum(nums[i], nums[i + 1], … , nums[j]))
  Constraints:0 <= nums.length <= 10^4-10^5 <= nums[i] <= 10^50 <= i <= j < nums.lengthAt most 10^4 calls will be made to sumRange.。/- 代码（一维）： /思路：前缀和1. 朴素的想法是循环累加nums[i]~nums[j]，然而由于会进行多次检索，因此为了降低检索的总时间应当降低时间复杂度2. 构造前缀和数组sums[i]，表示从nums[0]~nums[i - 1]的累加和/class NumArray {private: vector sums;public: NumArray(vector& nums) { int n = nums.size(); sums.resize(n + 1); for (int i = 0; i < n; ++i) sums[i + 1] = sums[i] + nums[i]; } int sumRange(int i, int j) { return sums[j + 1] - sums[i]; }};- 代码（二维）（容斥原理）： /思路：类似于一维前缀和，构造二维前缀和注意容斥原理/class NumMatrix {private: vector> sums;public: NumMatrix(vector>& matrix) { int m = matrix.size(); if (m > 0) { int n = matrix[0].size(); sums.resize(m + 1, vector(n + 1)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) sums[i + 1][j + 1] = sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + matrix[i][j]; } } int sumRegion(int row1, int col1, int row2, int col2) { return sums[row2 + 1][col2 + 1] - sums[row1][col2+1] - sums[row2+1][col1] + sums[row1][col1]; } };