如何降低数组区间求和与点更新操作问题的时间复杂度

解法优化思路 #

这个问题属于典型的单点修改+区间求和场景，你当前的暴力解法每次区间求和都需要遍历对应区间，当数组长度和查询量都较大时时间复杂度会达到O(nq)，性能很差。而普通前缀和数组虽然可以O(1)查区间和，但单点修改需要O(n)更新前缀数组，同样不适合有大量修改操作的场景。

这里推荐用树状数组（Fenwick Tree/二进制索引树） 实现，单点修改和区间求和的时间复杂度都可以降到O(logn)，整体时间复杂度优化为O(nlogn + qlogn)，可以应对大规模数据输入。

优化后代码实现 #

class FenwickTree {
  constructor(size) {
    this.n = size;
    this.tree = new Array(this.n + 1).fill(0); // 树状数组默认从下标1开始存储
  }

  // 在下标i的位置加delta
  update(i, delta) {
    i += 1; // 原数组是0下标，转换为树状数组的1下标
    while (i <= this.n) {
      this.tree[i] += delta;
      i += i & -i;
    }
  }

  // 查询原数组[0, i]的前缀和
  query(i) {
    i += 1; // 原数组是0下标，转换为树状数组的1下标
    let sum = 0;
    while (i > 0) {
      sum += this.tree[i];
      i -= i & -i;
    }
    return sum;
  }

  // 查询原数组[l, r]的区间和
  rangeQuery(l, r) {
    return this.query(r) - (l > 0 ? this.query(l - 1) : 0);
  }
}

function solution(v, q) {
  const answer = [];
  const ft = new FenwickTree(v.length);
  // 初始化树状数组
  for (let i = 0; i < v.length; i++) {
    ft.update(i, v[i]);
  }

  for (const [a, b, c] of q) {
    if (a === 1) {
      // 区间求和
      answer.push(ft.rangeQuery(b, c));
    } else if (a === 2) {
      // 单点修改：先算差值，再更新树状数组和原数组
      const delta = c - v[b];
      ft.update(b, delta);
      v[b] = c;
    }
  }
  return answer;
}

逻辑说明 #

1. 树状数组初始化阶段会遍历原数组一次，每个元素执行O(logn)的更新操作，总耗时O(nlogn)
2. 处理每个查询时：
   • 类型1的区间求和操作：两次前缀和查询做差得到结果，耗时O(logn)
   • 类型2的单点修改操作：计算新旧值的差值后更新树状数组，耗时O(logn)
3. 完全兼容你给出的示例输入，运行结果和暴力解法一致。

如果不需要复用树状数组逻辑，也可以把树状数组的实现直接整合到solution函数里减少代码量，逻辑不变。

内容的提问来源于stack exchange，提问作者JunKim