线段树和树状数组

1.线段树

线段树适用于区间操作较为复杂或者需要处理多个不同类型的区间操作的场景。具体如下：

• 区间求和、区间最值查询
• 区间更新
• 复杂的动态区间操作（区间最大公约数、最小公倍数）
• 支持懒标记的区间更新（更新无需遍历整个区间）

代码模板

class SegmentTree{
    //存储线段树的数组
    private int[] tree;
    //存储原始数据的数组
    private int[] data;
    //构造初始化
    public SegmentTree(int[] data){
        this.data = data;
        this.n = data.length;
        tree = new int[n*4];
        build(0,0,n-1);
    }
    private void build(int node, int start, int end){
        if(start == end){
            //叶子节点
            tree[node]= data[start];
        }else{
            int mid = (start+end)/2;
            int leftChild = 2*node + 1;
            int rightChild = 2*node + 2;
            build(leftChild, start, mid);
            build(rightChild, mid+1, end);
            tree[node] = tree[leftChild] + tree[rightChild]; // 区间和
        }
    }
    private int query(int L, int R){
        return query(0,0,n-1,L,R);
    }
    private int query(int node, int start, int end, int L, int R){
        if(R<start || L>end){
            return 0;
        }
        if(L<=start && end<=R){
            return tree[node];
        }
        int mid = (start + end) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        int leftSum = query(leftChild, start, mid, L, R);
        int rightSum = query(rightChild, mid + 1, end, L, R);
        return leftSum + rightSum;
    }
    
    //单点更新，将data[index]的值更新为val
    public void update(int index, int val) {
        update(0, 0, n - 1, index, val);
    }
    private void update(int node, int start, int end, int index, int val) {
        if (start == end) {
            data[index] = val;
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            int leftChild = 2 * node + 1;
            int rightChild = 2 * node + 2;
            if (index <= mid) {
                update(leftChild, start, mid, index, val);
            } else {
                update(rightChild, mid + 1, end, index, val);
            }
            tree[node] = tree[leftChild] + tree[rightChild]; // 更新区间和
        }
    }
}

2.树状数组

树状数组的应用场景多集中在需要快速处理单点更新、区间查询的场景，尤其是在操作相对简单且要求较少的情况下。

• 前缀和查询
• 单点更新+区间查询
• 动态数组操作

Class FenwickTree{
    private int[] tree;
    private int n;
    public FenwickTree(int n) {
        this.n = n;
        // 树状数组从索引1开始，0索引不用
        tree = new int[n + 1]; 
    }
     // 单点更新，将index处的值加上val
    public void update(int index, int val) {
        while (index <= n) {
            tree[index] += val;
            index += index & -index; // 更新父节点
        }
    }
    // 前缀和查询 [1, index]
    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index; // 访问父节点
        }
        return sum;
    }
    // 区间和查询 [L, R]
    public int queryRange(int L, int R) {
        return query(R) - query(L - 1);
    }
}