前缀和适用于数组不变适用于单点更新，区间查询
| 方法 | 构造 | 查询 | 修改 | 适用 |
|---|---|---|---|---|
| 前缀和 | O(n) | O(1) | 数组不变 | |
| 树状数组 | O(nlogn) | O(logn) | O(logn) | 区间查询，单点更新 |
307. 区域和检索 - 数组可修改 - 力扣（LeetCode）
-
数组不变，求区间和：「前缀和」、「树状数组」、「线段树」
-
多次修改某个数（单点），求区间和：「树状数组」、「线段树」
-
多次修改某个区间，输出最终结果：「差分」
-
多次修改某个区间，求区间和：「线段树」、「树状数组」（看修改区间范围大小）
-
多次将某个区间变成同一个数，求区间和：「线段树」、「树状数组」（看修改区间范围大小）