跳至主要內容

树状数组

2023年12月17日大约 2 分钟

树状数组

题目难度
307. 区域和检索 - 数组可修改中等单点更新，区间查询
315. 计算右侧小于当前元素的个数困难逆序对 见：离散化
剑指 Offer 51. 数组中的逆序对困难逆序对 见：离散化

思路

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

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

这样看来，「线段树」能解决的问题是最多的，那我们是不是无论什么情况都写「线段树」呢？

答案并不是，而且恰好相反，只有在我们遇到第 4 类问题，不得不写「线段树」的时候，我们才考虑线段树。

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

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

  1. 简单求区间和，用「前缀和」
  2. 多次将某个区间变成同一个数，用「线段树」
  3. 其他情况，用「树状数组」

307. 区域和检索 - 数组可修改

public class Solution307 {  static class NumArray {  private final Fenwick fenwick;   public NumArray(int[] nums) {  fenwick = new Fenwick(nums);  }   public void update(int index, int val) {  int add = val - fenwick.getSum(index, index);  fenwick.add(index + 1, add);  }   public int sumRange(int left, int right) {  return fenwick.getSum(left, right);  }   private static class Fenwick {  private final int n;  private final int[] tree;   public Fenwick(int n) {  this.n = n;  this.tree = new int[n + 1];  }   // O(n) 建树  public Fenwick(int[] nums) {  this.n = nums.length;  this.tree = new int[n + 1];  for (int i = 1; i <= n; i++) {  tree[i] += nums[i - 1];  int j = i + lowbit(i);  if (j <= n) {  tree[j] += tree[i];  }  }  }   int lowbit(int x) {  return x & -x;  }   // nums[x] add k  void add(int x, int k) {  while (x <= n) {  tree[x] += k;  x += lowbit(x);  }  }   // nums [1,x] 的和  int getSum(int x) {  int ans = 0;  while (x > 0) {  ans += tree[x];  x -= lowbit(x);  }  return ans;  }   // nums [l,r] 的和  int getSum(int l, int r) {  return getSum(r + 1) - getSum(l);  }  }  } }

参考链接

（全文完）