1，对比

• https://blog.csdn.net/honghuidan/article/details/77527808
• 两者相同点：单点/区间修改，区间查询
  • 区间查询：前缀和
  • 区间修改，单点查询：差分
  • 单点修改，区间查询：树状数组，线段树
  • 区间修改，区间查询：线段树+懒标记
• 不同点：
  • 树状数组只能维护前缀操作和(前缀和，前缀积，前缀最大最小)，而线段树可以维护区间操作和。
  • 树状数组：
    • 某些操作是存在逆元的，这样就给人一种树状数组可以维护区间信息的错觉:维护区间和，模质数意义下的区间乘积，区间xor和。能这样做的本质是取右端点的前缀和，然后对左端点左边的前缀和的逆元做一次操作，所以树状数组的区间询问其实是在两次前缀和询问。
    • 所以我们能看到树状数组能维护一些操作的区间信息但维护不了另一些的:最大/最小值，模非质数意义下的乘法，原因在于这些操作不存在逆元，所以就没法用两个前缀和做区间查询。
  • 线段树
    • 线段树就不一样了，线段树直接维护的就是区间信息，所以一切满足结合律的操作都能维护区间和，并且lazy标记的存在还能使线段树能够支持区间修改，这点是树状数组做不到的。
    • 可以说树状数组能做的事情其实是线段树的一个子集，大多数情况下使用树状数组真的只是因为它好写并且常数小而已。
    • 不过随着zkw线段树的普及，树状数组仅有的两点优势也不复存在了……估计要成为时泪了吧。

2，前缀和

3，差分

4，树状数组

5，线段树

• https://leetcode.cn/problems/my-calendar-iii/solution/xian-duan-shu-by-xiaohu9527-rfzj/
  • 懒标记：将节点的值加一，表示节点所表示的区间内的所有元素都加了一，而不是去具体修改每一个元素值。（例如：节点表示区间最大值的时候就很好用）
  • 懒标记使得线段树支持区间修改。
• 线段树将更新和查询的时间复杂度都变为O(logn)
• 线段树的结构：
  • 基于原数组，生成一个新的数组表示线段树的结构
  • 树的根节点在新数组index=1处
  • 新数组中所有节点（索引为index）的左右子节点分别为2*index，2*index+1
  • 原数组中的每一个元素在线段树数组中都是叶子节点，线段树数组中的其他节点（非叶子节点）表示都是原数组的一段区间和，根节点存储整个原数组的和（这里有两个数组，一个原数组，一个基于原数组生成的线段树数组）
• 查询操作
  • 根据查询区间，从新数组的根结点（index=1）出发，递归地向两边扩展（2*index, 2*index+1），在子树中找到合适的区间和返回，时间复杂度O(logn)
• 更新操作
  • 根据修改的节点，从新数组对应的叶子节点出发，一直更新其父节点直到更新根节点，时间复杂度O(logn)
• 代码实例：

//没有懒标记，单点修改，区间查询
import java.util.Arrays;

public class test {

    /**
     * 基于原数组生成线段树数组
     * @param arr   原数组
     * @param tree  生成的线段树数组
     * @param start 当前阶段处理的原数组起始索引（区间和起始索引）
     * @param end   当前阶段处理的原数组结束索引（区间和结束索引）
     * @param node_idx  与[start, end]相对应的区间和在线段树数组中的索引
     */
    public static void build_tree(int[] arr, int[] tree, int start, int end, int node_idx){
        if(start==end){
            //此时到达叶子节点
            tree[node_idx] = arr[start];
            return;
        }
        int leftNode_idx = 2*node_idx;
        int rightNode_idx = 2*node_idx+1;
        int middle = (start+end)/2;
        build_tree(arr, tree, start, middle, leftNode_idx);
        build_tree(arr, tree, middle+1, end, rightNode_idx);
        tree[node_idx] = tree[leftNode_idx]+tree[rightNode_idx];    //后序
    }

    /**
     * 由线段树数组查询得到原数组区间和
     * @param arr   原数组
     * @param tree  线段树数组
     * @param start 当前阶段处理的原数组起始索引
     * @param end   当前阶段处理的原数组结束索引
     * @param l 要查询的区间和的原数组起始索引
     * @param r 要查询的区间和的原数组结束索引
     * @param node_idx  与[start, end]相对应的区间和在线段树数组中的索引
     * @return
     */
    public static int query(int[] arr, int[] tree, int start, int end, int l, int r, int node_idx){
        if(l>end||r<start){
            //要查询的区间超出了当前区间的范围
            return 0;
        }else if(l<=start && end<=r){
            //要查询的区间覆盖了当前的区间范围
            return tree[node_idx];
        }else{
            int leftNode_idx = node_idx*2;
            int rightNode_idx = node_idx*2+1;
            int middle = (start+end)/2;
            int left_sum = query(arr, tree, start, middle, l, r, leftNode_idx);
            int right_sum = query(arr, tree, middle+1, end, l, r, rightNode_idx);
            return left_sum+right_sum;
        }
    }

    /**
     * 线段树单点修改-和建树很像
     * @param arr   原数组
     * @param tree  线段树数组
     * @param start 当前阶段处理的原数组起始索引
     * @param end   当前阶段处理的原数组结束索引
     * @param node_idx  与[start, end]相对应的区间和在线段树数组中的索引
     * @param update_idx    要修改的元素在原数组中的索引
     * @param val   原数组元素修改后的值
     */
    public static void update(int[] arr, int[] tree, int start, int end, int node_idx, int update_idx, int val){
        if(start==end){
            //修改点即可
            arr[start] = tree[node_idx] = val;
        }else{
            int leftNode_idx = node_idx*2;
            int rightNode_idx = node_idx*2+1;
            int middle = (start+end)/2;
            if(update_idx>middle){
                //要更新的值在右子树
                update(arr, tree, middle+1, end, rightNode_idx, update_idx, val);
            }else{
                //要更新的值在左子树
                update(arr, tree, start, middle, leftNode_idx, update_idx, val);
            }
            tree[node_idx] = tree[leftNode_idx]+tree[rightNode_idx];
        }
    }


    public static void main(String[] args) {
        int[] a = {10, 11, 12, 13, 14, 15};

        //生成线段树
        int[] tree = new int[a.length*4];
        build_tree(a, tree, 0, a.length-1, 1);
        System.out.println("生成的线段树为"+Arrays.toString(tree));

        //区间查询
        int l=0;
        int r=a.length-1;
        System.out.println(query(a, tree, 0, a.length-1, l, r, 1));

        //区间修改
        update(a, tree, 0, a.length-1, 1, a.length-1, 20);
        System.out.println("修改后的线段树为"+Arrays.toString(tree));
        System.out.println(query(a, tree, 0, a.length-1, l, r, 1));
    } 
}

• 例题：
  • 307. 区域和检索 - 数组可修改
  • 732. 我的日程安排表 III