给你一个数组 nums ，请你完成两类查询。

  1. 其中一类查询要求 更新 数组 nums 下标对应的值
  2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right

实现 NumArray 类：

  • NumArray(int[] nums) 用整数数组 nums 初始化对象
  • void update(int index, int val) 将 nums[index] 的值 更新 为 val
  • int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）

示例 1：

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

提示：

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • 调用 update 和 sumRange 方法次数不大于 3 * 104

树状数组

树状数组概述

树状数组或二元索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。它可以以的时间得到任意前缀和，并同时支持在时间内支持动态单点值的修改。空间复杂度。

按照Peter M. Fenwick的说法，正如所有的整数都可以表示成2的幂和，我们也可以把一串序列表示成一系列子序列的和。采用这个想法，我们可将一个前缀和划分成多个子序列的和，划分的方法就是采用数的2进制划分。这样，子序列的个数是其二进制表示中1的个数。

比如14=11102，我们可以将其划分为三个子序列，长度分别为8=10002，4=1002，2=102。即要求[0, 14)的元素和，我们可以求出[0, 8)的和、[8, 12)的和、[12, 14)的和，再将其相加。

lowbit函数

定义一个lowbit函数，返回参数的二进制中，最后一个1的位置所代表的数值。

例如，lowbit(34=00100010)的返回值是2；而lowbit(12=1100)返回4；lowbit(8=1000)返回8。

代码实现如下：

int lowbit(int x) {
    return x & (-x);
}

简要分析一下这么写的原理。我们知道对于任意一个二进制数（1后面跟着全0），取反加将得到其本身，因此，如果我们将一个数与其补码进行按位与，除了低位的会保留之外，高位的部分将因为取反而直接清零，因此就留下了二进制数中的最低位的。

树状数组实现

有了lowbit函数，我们就可以方便地从数字中提取最低位的1了。

首先给出树状数组的概念：定义数组sum为树状数组，nums为原数据数组，则sum满足以下性质：

  • sum[x]存储的是nums数组区间的值。

亦即，nums数组从下标开始，连续个数的和。比如，sum数组中下标为存储的是nums数组从下标开始，连续个数的和，即区间的和。

根据定义，不难知道树状数组的下标范围是，而nums数组的下标范围是。

tree_arr.drawio
tree_arr.drawio

上图展示了树状数组的结构和sum[i]之间的包含关系。如sum[4]所管辖的区间下包含了sum[1]，sum[2]和sum[3]这三个子区间。

这里可以观察得出一些特点：

  • 对于一个数num[i]，包含这个数的最小区间就是sum[i+1]。
  • 由子区间查询父区间的技巧：假设子区间的下标为i，则其父区间的下标为i + lowbit(i)。

查询

假设我们想查询区间的和，我们只需要查询区间和的和，然后将它们相加即可。前者对应sum数组中下标为的值，后者对应sum数组中下标为的值。

实现查询算法的思路是，每次取对应sum[n]的值，然后从中减去，直到等于。

public int getSum(int n) {
  if (n > MAX_N) n = MAX_N - 1; // 超出上界的情况
  int total = 0;
  for (int i = n; i > 0; i -= lowbit(i))
  	toal += sum[i];
  return total;
}

更新

更新时，我们首先计算出变化值delta，然后将所有包含被更新下标的区间和加上变化值delta。

tree_arr_update.drawio
tree_arr_update.drawio

更新的过程是，首先查询出包含该数的最小区间，然后依次向上更新父区间。

public void update(int index, int val) {
  // re-compute the sum.
  int delta = val - nums[index];
  nums[index] = val;
  // 所有包含被更新的下标的区间都要更新
  for (int i = index + 1; i < MAX_N; i += lowbit(i)) {
  	sum[i] += delta;
  }
}

新建

始终记住，树状数组中的下标表示原数组中中元素的累积和。区间是左闭右开的。因此，树状数组的长度应该比原数组长度大。

朴素建树算法如下，即按照树状数组的定义构建。

int[] sum, nums;

int MAX_N; // 树状数组的长度 MAX_N = nums.length + 1

void build() {
  // build preSum(tree-like array)
  for (int i = 1; i < MAX_N; i++) {
    for (int j = i - lowbit(i); j < i; j++) {
      sum[i] += nums[j];
    }
  }
}

除了标准建树方法外，还存在的建树方法。

观察上图，每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献，即每次确定完儿子的值后，用自己的值更新父亲。

// O(n)建树
void build() {
  for (int i = 1; i < MAX_N; ++i) {
    sum[i] += nums[i - 1];
    int j = i + lowbit(i);
    if (j < MAX_N) sum[j] += sum[i];
  }
}

其他应用

求逆序对数

逆序对数是一个数列中在它前面有比它大的个数。如4312的逆序对数是0+1+2+2=5。此问题可以用树状数组解决。