Q1题目链接：https://leetcode.com/problems/range-sum-query-immutable/
leetcode 303
看到题目的第一思路：
代码随想录之后的想法和总结：
如何用 prefix 查询区间和？
如果你想查询：nums[left] + nums[left+1] + ... + nums[right]
可以用公式：
sumRange(left, right) = prefix[right + 1] - prefix[left]
唯一要注意的是 要在前缀和数组前面加一个索引，也就是比数组多一个索引
时间复杂度以及空间复杂度：
🧮 初始化阶段：__init__(self, nums: List[int])
时间复杂度：O(n)
-
n是输入数组nums的长度。 -
因为你只循环了一遍数组，计算前缀和，所以是 线性时间。
空间复杂度：O(n)
-
self.preSum数组的长度是n + 1，所以占用了额外的线性空间。
🔍 查询阶段：sumRange(left, right)
时间复杂度：O(1)
-
你只做了一次减法：
preSum[right+1] - preSum[left] -
所以无论查询区间多大，时间始终是常数级。
空间复杂度：O(1)
-
不需要分配额外空间，仅使用已有数组
“这种方式用空间换时间，通过一次性预处理前缀和，使查询操作从 O(n) 降到 O(1)，适用于大量查询的场景。”
Q2题目链接：https://leetcode.com/problems/range-sum-query-2d-immutable/
leetcode 304
看到题目的第一思路：
好难 之后再回来看一下这题
代码随想录之后的想法和总结：
最主要是这个方法的应用
时间复杂度以及空间复杂度：
Q3题目链接：https://leetcode.com/problems/corporate-flight-bookings/
leetcode 1109 航班预订问题
看到题目的第一思路：
可以把这个题目变相理解为差分数组的问题：给你输入一个长度为 n 的数组 nums，其中所有元素都是 0。再给你输入一个 bookings，里面是若干三元组 (i, j, k)，每个三元组的含义就是要求你给 nums 数组的闭区间 [i-1,j-1] 中所有元素都加上 k。请你返回最后的 nums 数组是多少？
代码随想录之后的想法和总结：
差分数组的原理：
-
diff[i] += 3：表示从下标i开始的所有元素都要加 3。 -
diff[j+1] -= 3：表示从下标j+1开始的元素都要恢复原来的值（即把之前加的 3 抵消）。
于是，这就实现了只在区间 [i..j] 加了 3，外面的不变。
把题目变相理解为差分数组其实就三个步骤
1 初始化一个原始数组 元素都为0，并且把题目要求的区间也初始化元素
2 构造差分数组，并且使用差分法对他进行区间加法
比如 初始化diff数组，给diff数组的中间元素[i,j]之间加上val
3 通过前缀和从差分数组diff还原出结果数组
| 方法/步骤 | 作用 |
|---|---|
__init__(nums) | 初始化差分数组 diff，支持后续快速区间加法 |
increment(i, j, v) | 把原数组中区间 [i..j] 每个元素加上 v，只修改差分数组 |
result() | 通过前缀和，从差分数组 |
时间复杂度以及空间复杂度：
时间：O(n) 初始化数组，构造差分数组，遍历元素，还原数组 都是O(n)
空间复杂度分析
1. 差分数组 self.diff 大小为 n
2. 返回的结果数组 res 也是 n
Q4题目链接：1094. Car Pooling
leetcode 1094 乘客上车问题
看到题目的第一思路：
可以转换成差分数组思路：把所有乘客的上车区间 [i, j]（即从 i 公里开始，到 j 公里之前结束）都叠加起来，得到每一公里车上实际有多少人，然后判断是否有超过车的容量的情况。
代码随想录之后的想法和总结：
相信你已经能够联想到差分数组技巧了：trips[i] 代表着一组区间操作，旅客的上车和下车就相当于数组的区间加减；只要结果数组中的元素都小于 capacity，就说明可以不超载运输所有旅客。
注意：
使用 j = trip[2] - 1 是因为：我们要计算每个站点车上的乘客,[i,j,val]也就分别表示乘客从i上车到j是还在车上的最后一站，这些时刻车上增加了多少乘客，如果trip[2]是区间这时乘客已经下车了，不能加到区间里面了
-
我们用的是 闭区间
[i, j]的差分数组逻辑 -
而题目给的上下车区间语义是 左闭右开
[from, to) -
所以要转换成闭区间，就变成了
[from, to - 1]
时间复杂度以及空间复杂度：
✅ 综合时间复杂度：
-
差分数组初始化：O(1)
-
遍历 trips：O(n)
-
还原数组：O(1)
-
检查是否超载：O(1)
总时间复杂度：O(n)，其中
n是trips的长度。
🧠 空间复杂度分析
-
nums数组固定长度为 1001 → O(1) -
diff数组长度为 1001 → O(1) -
res数组长度为 1001 → O(1)
你没有使用与 n 相关的额外空间，所有数组长度固定（最多 1001）。
总空间复杂度：O(1)（常数空间）
今日收获，学习时长：
重点学习了两个数组中的技巧：
前缀和技巧：原始数组不会被修改的情况下，频繁查询某个区间的累加和
差分数组技巧：频繁对原始数组的某个区间元素进行增减
前缀和技巧有几个局限性：
第一个局限性：使用前缀和技巧的前提是原数组 nums 不会发生变化。
如果原数组中的某个元素改变了，那么 preSum 数组中该元素后面的值就会失效，需要重新花费 O(n)O(n) 的时间计算 preSum 数组，这就和普通的暴力解法没太大区别了。
第二个局限性：前缀和技巧只适用于存在逆运算的场景。
比方说求和的场景，你知道 x+6=10x+6=10，那么可以推导出 x=10−6=4x=10−6=4，求乘积的场景也是类似的，你知道 x∗6=12x∗6=12，那么可以推导出 x=12/6=2x=12/6=2，这就叫存在逆运算，都可以使用前缀和技巧。
但有些场景是没有逆运算的，比方说求最大值的场景，你知道 max(x,8)=8max(x,8)=8，此时你无法推导出 xx 的值。
差分数组的优缺点：
| 优势 | 说明 |
|---|---|
| 🟢 区间修改效率高 | 原本要对一个区间的所有元素做修改，差分数组只需修改两个端点，时间复杂度从 O(n) → O(1)。 |
| 🟢 代码实现简单、空间利用率高 | 只需维护一个额外的数组（差分数组），不需要复杂的数据结构。 |
| 🟢 不破坏原数组结构 | 原始数组通过差分数组+前缀和可以随时还原。 |
| 注意点 | 说明 |
|---|---|
| ✅ 差分数组适合只做区间加减修改，不适合频繁查询单个值时使用（除非先恢复）。 | |
| ✅ 差分数组不适合动态修改（如删除某一段修改），要使用更复杂的数据结构（如树状数组、线段树）。 | |
| ✅ 最终结果数组要通过 前缀和还原 才能得出正确值。 |
