针对不同的题目，我们有不同的方案可以选择（假设我们有一个数组）：

    1. 数组不变，求区间和：「前缀和」、「树状数组」、「线段树」
    2. 多次修改某个数（单点），求区间和：「树状数组」、「线段树」
    3. 多次修改某个区间，输出最终结果：「差分」
    4. 多次修改某个区间，求区间和：「线段树」、「树状数组」（看修改区间范围大小）
    5. 多次将某个区间变成同一个数，求区间和：「线段树」、「树状数组」（看修改区间范围大小）

    「线段树」代码很长，而且常数很大，实际表现不算很好。我们只有在不得不用的时候才考虑「线段树」。

    总结一下，我们应该按这样的优先级进行考虑：

    1. 简单求区间和，用「前缀和」
    2. 多次将某个区间变成同一个数，用「线段树」
    3. 其他情况，用「树状数组」 ```csharp // 上来先把三个方法写出来 { int[] tree; int lowbit(int x) {
      1.  return x & -x;
      } // 查询前缀和的方法 int query(int x) {
       int ans = 0;
 for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
 return ans;
      } // 在树状数组 x 位置中增加值 u void add(int x, int u) {
       for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
      } }

    // 初始化「树状数组」，要默认数组是从 1 开始 { for (int i = 0; i < n; i++) add(i + 1, nums[i]); }

    // 使用「树状数组」： {
    void update(int i, int val) { // 原有的值是 nums[i]，要使得修改为 val，需要增加 val - nums[i] add(i + 1, val - nums[i]); nums[i] = val; }

    int sumRange(int l, int r) {
    return query(r + 1) - query(l);
}

    } ```