遇到“连续一段”的问题，先区分范围是否固定、元素能否修改、查询是否在线。静态区间求和与频繁修改后的区间求和，虽然输出相似，需要的结构可能完全不同。

前缀和与差分互为视角

定义 P[0]=0、P[i+1]=P[i]+a[i]，半开区间 [l,r) 的和就是 P[r]-P[l]。预处理 O(n)，每次查询 O(1)；中途修改一个元素，会影响其后的所有前缀，直接维护不再便宜。

若只批量做区间加法，最后统一取值，可在差分数组的左右端点记变化：D[l]+=x、D[r]-=x，最终前缀累加恢复。右端点等于n时需要额外一个位置或明确跳过。差分并不直接支持任意时刻的区间总和，在线查询需增加结构。

滑窗也需要单调性

正数数组中寻找和不超过某阈值的最长窗口，右端加入会增加总和，左端移除会减少总和，才能按违规条件持续收缩。含负数时这一关系失效，例如负数可能让更长窗口重新合法，不能机械套用同一规则。

固定窗口最大值可以维护候选下标的单调队列。新值加入时，队尾不比它大的旧值可以删除，因为新值更大且更晚离开窗口；队首若已过期就移除，剩余队首始终是当前最大候选。每个下标至多进出一次，总时间 O(n)。

树状数组维护可更新的前缀

树状数组使用一基下标，位置i保存长度为 i & -i 的末尾区间。查询前缀时不断减去这个最低有效位，把区间分成互不重叠的块；单点更新时不断加上最低有效位，更新所有覆盖该点的块。两者都访问 O(log n) 个位置。

from collections import deque


class Fenwick:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (self.n + 1)
        for index, value in enumerate(values):
            self.add(index, value)

    def add(self, index, delta):
        if not 0 <= index < self.n:
            raise IndexError(index)
        index += 1
        while index <= self.n:
            self.tree[index] += delta
            index += index & -index

    def prefix(self, end):
        if not 0 <= end <= self.n:
            raise IndexError(end)
        answer = 0
        while end:
            answer += self.tree[end]
            end -= end & -end
        return answer

    def range_sum(self, left, right):
        if not 0 <= left <= right <= self.n:
            raise IndexError((left, right))
        return self.prefix(right) - self.prefix(left)


def sliding_maximum(values, k):
    if not 1 <= k <= len(values):
        raise ValueError('k must be between 1 and len(values)')
    candidates, answer = deque(), []
    for i, value in enumerate(values):
        while candidates and candidates[0] <= i - k:
            candidates.popleft()
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(i)
        if i >= k - 1:
            answer.append(values[candidates[0]])
    return answer


if __name__ == '__main__':
    sums = Fenwick([2, 1, 4, 3])
    print(sums.range_sum(1, 4))
    sums.add(2, 5)
    print(sums.range_sum(1, 4))
    print(sliding_maximum([1, 3, 2, 5, 4], 3))

对 [2,1,4,3] 的 [1,4) 查询得到8，把下标2增加5后得到13。外部接口统一用零起始半开区间，避免把内部一基技巧扩散到调用方。区间和可由两个前缀相减，因为加法有逆操作；区间最小值不能简单用“两个前缀最小值相减”得到。

结构选择与约束

线段树把范围递归拆成左右区间，可维护满足结合律的合并结果，点更新与区间查询通常 O(log n)。要支持区间赋值或加法，可进一步设计延迟标记，但标记组合顺序和区间长度都影响正确性。静态查询、离线批处理、点更新、区间更新应分别建模，不能默认最复杂结构总是最好。

单调栈常求某个元素左右最近的更大或更小值，存储尚未找到答案的候选；单调队列则额外处理滑窗过期。维护的是候选可被支配的关系，不是对输入排序，原有位置关系必须保留。

练习与面试自查

用普通列表作为基线，随机执行点增加和区间查询，与树状数组逐步对拍。窗口最大值用每个切片的 max 做基线，检查K=1、K=n、全相等、递增、递减及K非法。

面试中解释：删除被新值支配的旧队尾为什么安全；为什么只比较值还不够，必须保存下标；一基树状数组若让更新从零开始为什么会无法前进。先写清区间约定再讨论位运算。

本地运行

示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：

python example.py
python -m unittest -v test_example.py

测试检查本文列出的边界；新增练习仍需自己补充断言。

参考资料