前缀和

前缀和.jpg
前缀和preSum[i]：表示在坐标i之前的所有数之和
preSum[j]-preSum[i]：坐标[i,j-1]的所有数之和

  1. let nums = [3, 5, 2, -2, 4, 1];
  2. /**
  3.  * @description: 求前缀和数组
  4.  * @return {*} 返回前缀和数组preSum
  5.  * @param {*} nums 传入的数组
  6.  */
  7. function prefixSum(nums) {
  8.     let preSum = [];
  9.     preSum[0] = 0;
  10.     for (let i = 0; i < nums.length; i++) {
  11.         preSum[i + 1] = preSum[i] + nums[i];
  12.     }
  13.     return preSum;
  14. }
  15. /**
  16.  * @description: 求[i,j)区间内的数组和
  17.  * @return {*} 数组和
  18.  * @param {*} preSum 前缀数组
  19.  * @param {*} i 左坐标
  20.  * @param {*} j 右坐标
  21.  */
  22. function sumFromTo(preSum,i,j) {
  23.     return preSum[j]-preSum[i];
  24. }

测试：

let preSum = prefixSum(nums);
let sum = sumFromTo(preSum,1,4)
console.log(sum); // 5

差分数组

差分数组.jpg
差分数组diff[i]：当前位置数-前一个位置数
从[i,j]的diff数组和：nums[j]-nums[i-1]

let nums = [8,2,6,3,1];
/**
 * @description: 求差分数组
 * @return {*} 返回差分数组diff
 * @param {*} nums 传入的数组
 */
function diff(nums) {
    let diffArray = [];
    diffArray[0]=nums[0];
    for(let i=1;i<nums.length;i++){
        diffArray[i]=nums[i]-nums[i-1];
    }
    return diffArray;
}
/**
 * @description: 让区间[i,j]内元素都加3
 * @param {*} diffArray 差分数组diff
 * @param {*} i 左坐标
 * @param {*} j 右坐标
 * @param {*} addNum 要加的数
 */
function diffAddNum(diffArray,i,j,addNum) {
    diffArray[i]+=addNum;
    diffArray[j+1]-=addNum;
}
/**
 * @description: 通过差分数组，找到原数组
 * @return {*} 原数组
 * @param {*} diffArray 差分数组
 */
function deDiff(diffArray) {
    let resNum = [];
    resNum[0]=diffArray[0];
    for(let i=1;i<diffArray.length;i++){
        resNum[i]=resNum[i-1]+diffArray[i];
    }
    return resNum;
}

测试：

console.log(nums);
let diffArray = diff(nums);
diffAddNum(diffArray,1,3,3);
console.log(diffArray);
let resNum = deDiff(diffArray);
console.log(resNum);
/***********************
[ 8, 2, 6, 3, 1 ]
[ 8, -3, 4, -3, -5 ]
[ 8, 5, 9, 6, 1 ]
**********************/