# 区间和与线段树

#### 区间和问题

对于不变数组的区间和问题可以通过前缀数组解决,

即一开始构建一个前缀和数组,当实际要求区间和的时候直接用传入的下标相减就行.要注意边界处理,为了方便一般在前缀数组头置0,然后取下标时用right+1 - left ,因为区间和包含开始节点,而直接减会把开始节点减掉.

#### [303. 区域和检索 - 数组不可变](https://leetcode.cn/problems/range-sum-query-immutable/)

```
var NumArray = function(nums) {
    this.subArr = [0]
    this.sub = 0
    nums.forEach(item =>{
        this.sub+=item
        this.subArr.push(this.sub)
    }) 
    console.log(this.subArr)
};

NumArray.prototype.sumRange = function(left, right) {
    return this.subArr[right+1] - this.subArr[left]
};
```

#### 记忆化 [560. 和为 K 的子数组](https://leetcode.cn/problems/subarray-sum-equals-k/)

和为k的子数组,其实参照上题的思路就是 subArr\[right] - subArr\[left] == k

当然为了统计总共有多少种,则需要引入一个map做为累加和结果的记录.

遍历前缀数组,作为结束下标,然后通过减 k 取可以满足的开始下标取值, 存在的话则记录结果 + 1 ,不存在就记录下当前节点的前缀和结果到map里,以为之后的查询做准备

```
var subarraySum = function(nums, k) {
  let subArr = []
  const mp = new Map();
  let res = 0
  let sub = 0
  mp.set(0,1)
  for(let I = 0; I < nums.length; I++){
    sub+=nums[I]
    subArr[i] = sub
  }
  subArr.forEach(item=>{
   if(mp.has(item - k)){
    res += mp.get(item - k);
   }
   if(mp.has(item)){
      mp.set(item, mp.get(item) + 1);
   } else {
    mp.set(item,1)
   }
  })
  return res
}; 
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dawn-inshadow.gitbook.io/life/suan-fa/qu-jian-he-yu-xian-duan-shu.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.