区间求和

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

区间求和是算法中非常常见的一个类型题目，一般有两个操作：

1. 单点更新
2. 区间求和

然后不同的题目会对上面两种操作的调用次数不同

1、普通方法

1.1、普通数组

• 单点更新：\(O(1)\)
• 区间求和：\(O(N)\)

1.2、前缀和数组

• 单点更新：\(O(N)\)
• 区间求和：\(O(1)\)

无论是哪一种方式，如果单点更新和区间求和的次数相当，并且都十分多时，效率是不高的。

但是如果某一种操作的调用次数非常高，可以使用对应的方式。

例如有些题目，数组初始化后就不再改变，只是不断地求区间和，就可以使用前缀和。

2、分块

分块的思想是，由于单点更新和区间求和的调用次数相当，所以希望尽可能平摊在两个操作上的时间复杂度

【操作】

1. 将数组分成 \(\sqrt{N}\) 块，每块有 \(\sqrt{N}\) 个元素
2. 单点更新：在某个块内遍历：\(O(\sqrt{N})\)
3. 区间求和：最多将 \(\sqrt{N}\) 个块加在一起：\(O(\sqrt{N})\)

3、树形数组

image-20221029210540933

/**
 * Binary Index Tree
 * 树状数组
 * 思想是: 前缀区间的差集
 */
public class BIT {
    private int[] tree;
    private int len;
    
    public BIT(int n){
        len = n + 1;
        tree = new int[len];
    }
    
    /**
     * 做单点更新
     * 要把包含了nums[i]的元素全部更新
     * @param i 下标
     * @param delta 增加的值
     */
    public void update(int i, int delta){
        i = i + 1;
        while (i < len){
            tree[i] += delta;
            i += lowbit(i);
        }
    }
    
    /**
     *
     * @param i 下标 i
     * @return 前 i 个元素之和
     */
    public int query(int i){
        int sum = 0;
        i = i + 1;
        while (i > 0){
            sum += tree[i];
            i -= lowbit(i); // 不断去掉(二进制表示下)最后一个1
        }
        return sum;
    }
    
    public int lowbit(int x){
        return x & (-x);
    }
}

4、线段树

image-20221029210553764

/**
 * 线段树
 * 用二分的方式来对树进行划分
 * 思想是: 若干区间的并集
 */
public class SegmentTree {
    int[] st;
    int n;
    public SegmentTree(int[] nums){
        buildTree(nums);
    }
    
    /*
    二叉树的性质:
            1、已知父节点下标 i，求出左右子节点的下标 i >> 1 和 (i >> 1) | 1
            2、已知左右子节点下标 i，求出父节点下标 i << 1
            3、对于完美二叉树来说，整棵树的节点总数 = 2 * 叶子节点总数
    从最底层开始建树
     */
    private void buildTree(int[] nums){
        n = nums.length;
        st = new int[2 * n];
        // 先构建叶子节点
        for (int i = n; i < 2 * n; i++){
            st[i] = nums[i - n];
        }
        // 构建非叶子节点
        for (int i = n - 1; i > 0; i--){
            // st[i << 1] 和 st[(i << 1) | 1] 分别代表 左子节点 和 右子节点
            st[i] = st[i << 1] + st[(i << 1) | 1];
        }
    }
    
    public void update(int index, int delta){
        index += n;
        while ( index > 0){
            st[index] += delta;
            index = index >> 1; // 向上找到父节点
        }
    }
    
    public int query(int l, int r){
        int sum = 0;
        l += n; r += n;
        for (; l <= r; l >>= 1, r >>= 1){
            if( (l & 1) == 1 ){ // l是右子节点
                sum += st[l];
                l++;
            }
            if( (r & 1) == 0 ){ // r是左子节点
                sum += st[r];
                r--;
            }
        }
        return sum;
    }
}