Task

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example

1
2
3
4
5

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

BIT

  • 对于prefix sum问题，使用BIT(Binary Indexed Tree，又叫Fenwick Tree，又叫树状数组)可实现O(log(n))时间内求解数组的prefix sum，并在数组中一个值发生变化时以O(log(n))的时间更新节点值

motivation

  • 假设要求数组x=[2,5,-1,3,6]的第i项到第j项和，可求数组的累计和得到s=[2,7,6,9,15]，用s[j]-s[i-1]即可
  • 但当数组中某个值发生变化时，必须重新求累计和，时间是O(n)
  • BIT的设计初衷是维护一个数据结构，使得：
    • 数组中某个数值发生变化时，可在O(log(n))时间内更新该数据结构
    • 需要数组前k项和时，可在该数据结构上以O(log(n))的时间求出结果
  • 维护一个树状结构，深度是O(log(n))：
    • 数值发生变化（update）时，从该位置对应节点向根部遍历，时间是O(log(n))
    • 求前k项和（query）时，从该位置对应节点向根部遍历，时间是O(log(n))

树状结构

  • 举个例子：对于数组[1,2,3,4,5,6,7,8]
  • update和query对应的数据结构不一样，如下图： leetcode307
  • 维护update tree：
    • 对于数组中的位置x（红色数字，索引从1开始），每个位置的父节点是位置为x+lowbit(x)的节点。根节点必是数组中最后一个位置
    • lowbit(x)是将x转换为二进制后，最低位的1及其后面的部分，快速计算方法：lowbit(x)=x&(-x)，其中负数使用补码，即-x=~x+1
    • 数组某个位置的值增加k时，将该位置对应节点向上直到根节点这条路径上的所有节点值都增加k（初始化时要做n次这样的操作）
  • 维护query tree：
    • 对于数组中的位置x（红色数字，索引从1开始），每个位置的父节点是位置为x-lowbit(x)的节点。根节点必是2的幂（因为减到最后，二进制形式中只剩下一个1）
    • 需要求前k项和时，将k对应节点向上直到根节点这条路径上的所有节点相加即是所求值
  • 时间复杂度：由于每次update/query时都是从叶子节点向根节点遍历，而数深度是O(log(n))，故update/query的时间复杂度都是O(log(n))
  • 空间复杂度：由于BIT本质上是比原数组多一个0索引的数组，故空间复杂度是O(n)

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class FenwickTree{
public:
    //对于长为n的数组，使用长为n+1的数组来存储BIT，因为BIT的索引从1开始。全初始化为0
    //使用update和query时不会访问索引为0的节点
    FenwickTree(int n): sums_(n+1,0) {}
    //更新位置i处的值（下标从1开始），对其增加delta
    void update(int i,int delta){
        //向上追溯到根节点，根节点必是数组的最后一个
        while(i<sums_.size()){
            sums_[i]+=delta;
            i+=lowbit(i);
        }
    }
    //求位置i处的前i项和（下标从1开始）
    int query(int i) const {
        int sum=0;
        //向上追溯到根节点，根节点必是减去lowbit后不为0的最后一个节点
        while(i>0){
            sum+=sums_[i];
            i-=lowbit(i);
        }
        return sum;
    }
private:
    //lowbit函数的内联实现
    static inline int lowbit(int x){return x&(-x);}
    //vector存储底层数据
    vector<int> sums_;
};

Solution

  • 直接使用上面的FenwickTree类
  • 时间复杂度：初始化时要对n个数值都update BIT，故时间复杂度是O(nlog(n))
  • 空间复杂度：每次修改一个值只需update一次，时间复杂度是O(log(n))
  • 实现：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// Runtime: 56 ms, faster than 67.51% of C++ online submissions for Range Sum Query - Mutable.
// Memory Usage: 19.2 MB, less than 25.00% of C++ online submissions for Range Sum Query - Mutable.
class NumArray {
public:
    //初始化两个底层数据，nums_用move是考虑性能，初始化tree_时用到nums_故声明顺序应是nums_在前
    NumArray(vector<int>& nums): nums_(std::move(nums)),tree_(nums_.size()) {
        for(int i=0;i<nums_.size();++i)
            //对每个位置都更新BIT
            tree_.update(i+1,nums_[i]);
    }
    void update(int i, int val) {
        //由于BIT的索引从1开始，故要+1
        tree_.update(i+1,val-nums_[i]);
        nums_[i]=val;
    }
    int sumRange(int i, int j) {
        //BIT的索引从1开始，故要+1
        return tree_.query(j+1)-tree_.query(i);
    }
private:
    //这两者声明顺序不可反，因为构造函数初值列表中初始化tree_时要用到nums_
    vector<int> nums_;
    FenwickTree tree_;
};
/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */