树状数组，用于快速求解范围区间的和

求解数组区间的和，有前缀和、差分数组、树状数组，但各所适用的场景不用。

前缀和适用于数组的值一开始固定不变的情况；
差分数组适用于数组的值会改变（增加|删除），但是求解原数据时需要恢复数据；
树状数组适用数组的值会改变，还可以快速求解一段区间的和，但需要构建数据结构。

树状数组模板

包括建树、查询区间值等。

// 直接上树状数组的结构
int[] tree;
int[] num;
int len;
public int lowbit(int x) {
    return x & (-x);
}
public void add(int index, int val) {
    while(index < len) {
        tree[index] += val;
        index += lowbit(index);
    }
}
public int query(int index) {
    int sum = 0;
    while (index > 0) {
        sum += tree[index];
        index -= lowbit(index);
    }
    return sum;
}
public NumArray(int[] nums) {
   num = nums;
   len = nums.length + 1; // 树状数组下标从1开始
   tree = new int[len];
   for (int i = 0; i < nums.length; i++) {
       add(i + 1, nums[i]);
   }
}

307.区域和检索 - 数组可修改（中等）

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

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

其中一类查询要求更新数组 nums 下标对应的值
另一类查询要求返回数组 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 * 10⁴
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
调用 update 和 sumRange 方法次数不大于 3 * 10⁴

思路

本题需要对数组区间求和，并且需要频繁修改数组中的值，排除前缀和，可以使用树状数组和线段树，但是能用树状数组优先使用树状数组，实现起来会更方便。
解题方法

直接上树状数组结构，然后放入实现类中即可。
复杂度
- 时间复杂度:
  
  $O(logn)$
- 空间复杂度:
  
  $O(n)$
Code

class NumArray {
    // 区间求和，如果数组的值不变，可以直接用前缀和，这里需要update数组内的单个值，可以优先考虑用树状数组实现比较简单，但是也可以用线段树
    // 直接上树状数组的结构
    int[] tree;
    int[] num;
    int len;
    public int lowbit(int x) {
        return x & (-x);
    }
    public void add(int index, int val) {
        while(index < len) {
            tree[index] += val;
            index += lowbit(index);
        }
    }
    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= lowbit(index);
        }
        return sum;
    }
    public NumArray(int[] nums) {
       num = nums;
       len = nums.length + 1; // 树状数组下标从1开始
       tree = new int[len];
       for (int i = 0; i < nums.length; i++) {
           add(i + 1, nums[i]);
       }
    }
    
    public void update(int index, int val) {
       // 计算需要更改的值为 val - num[index]
       add(index + 1, val - num[index]);
       num[index] = val;
    }
    
    public int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */

1893.检查是否区域内所有整数都被覆盖（简单）

Problem: 1893. 检查是否区域内所有整数都被覆盖

给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [start_i, end_i] 表示一个从 start_i 到 end_i 的 闭区间 。

如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖，那么请你返回 true ，否则返回 false 。

已知区间 ranges[i] = [start_i, end_i] ，如果整数 x 满足 start_i <= x <= end_i ，那么我们称整数x 被覆盖了。

示例 1：

输入：ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
输出：true
解释：2 到 5 的每个整数都被覆盖了：
- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。

示例 2：

输入：ranges = [[1,10],[10,20]], left = 21, right = 21
输出：false
解释：21 没有被任何一个区间覆盖。

提示：

1 <= ranges.length <= 50
1 <= start_i <= end_i <= 50
1 <= left <= right <= 50

思路

可以把两个整数 left 和 right的区间[left, right]分别拆开看做每个单独的区间[i]，取[i]在ranges区间的值是否不等于0，如果不等于0则说明ranges已覆盖。
解题方法

套用树状数组，对ranges里的区间range [i…j],都初始化到树状数组中，固定 add 值 1，query查询时，然后判断值是否为0。
复杂度
- 时间复杂度:
  
  建树的时间复杂度：跟ranges和里面的range长度、lowbit的时间有关，n最大为50，最大的时间复杂度为$O(nnlogC)$；查询query的时间复杂度为$O(nlogC)$
- 空间复杂度:
  
  $O(C)$
Code


class Solution {
    // 用树状数组解答，查询区间内是否有值
    int[] tree;
    int len;
    public boolean isCovered(int[][] ranges, int left, int right) {
        len = 51;
        tree = new int[len];
        // 建树
        for(int[] range: ranges) {
            int lr = range[0], rr = range[1];
            while(lr <= rr) {
                add(lr, 1);
                lr++;
            }
        }
        for(int i = left; i <= right; i++) {
            if (query(i) - query(i -1) == 0) return false;
        }
        return true;
    }
    public int lowbit(int x) {
        return x & -x;
    }
    public void add(int index, int val) {
        while(index < len) {
            tree[index] += 1;
            index += lowbit(index);
        }
    }
    public int query(int x) {
        int sum = 0;
        while(x > 0) {
            sum += tree[x];
            x -= lowbit(x);
        }
        return sum;
    }
}