区间求和专题

1.树状数组->「单点修改 & 区间查询」：

先输入一个长度为n的数组nums，有如下两种操作：

1.输入一个数m，输出数组中下标1~m的前缀和sum[1,m]

2.对某个指定下标的数进行值的修改

常规方法：前缀和，但是当单点修改的次数增多，前缀和更新耗时O(N)，然后再求sum[1,m]，总体时间复杂度为O(N^2)

进阶方法：树状数组和线段树可以达到单次操作logN级别。平均时间复杂度O(NlogN)

7=0111=0100+0010+0001=lowBit(7)+lowBit(3)+lowBit(1)

前置知识：二进制区间分解lowBit(x)=x^(-x)求出x中仅保留最低位的1的数值，lowBit(7)=0100=4

int lowbit(int x) {
    return x & -x;
}

概念：树状数组就是一种基于二进制思想的数据结构，基本用途是维护序列的前缀和。

对于给定的序列a，设树状数组为c，则c[x]保存序列a的区间[x-lowbit(x)+1,x]中所有数的和

int[] tr = new int[n];

主要有以下两个基本操作:

(1) update，单点修改，修改序列a中的某个元素;

(2) query，区间查询，查询序列a中区间[1,x]的所有数的和。

操作1:区间查询query

树状数组能够完成的是查询前缀和，相减即可得到区间和。

利用c[x]维护的是序列a中[x-lowbit(x)+1,x]的区间和，然后不断向前寻找即可，时间复杂度为O(logN)。

int query(int x) {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i)) ans += tr[i];
    return ans;
}

操作2:单点修改update

单点修改更准确的说是“单点增加”，给序列a中的一个数a[x]加上t，然后要更新树状数组c维护的前缀和，只需要不断向上维护c[x]的父亲结点即可，时间复杂度为O(logN)。

void add(int x, int u) {
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += u;
}

注意：这里都默认索引从1开始

思考:如何初始化树状数组?

方法一:输入序列a等价于对a进行单点修改，更新树状数组即可，时间复杂度为O(NlogN)。

for (int i = 0; i < nums.length; i++) {
    add(i, 1);
}

方法二:考虑每个结点对父亲结点的贡献，时间复杂度为O(N)。

for (int i = 0; i < nums.length; i++) {
    tr[i] += nums[i];
    if (i + lowBit(i) <= n) tr[i + lowBit(i)] += tr[i];
}

三叶姐树状数组模板：

一篇不错的图解：[树状数组] 详解树状数组, 包含更新查询图解, 秒懂lowbit含义(JAVA 65ms, 68.6MB)

// 上来先把三个方法写出来
{
    int[] tree;
    int lowbit(int x) {
        return x & -x;
    }
    // 查询前缀和的方法
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
    // 在树状数组 x 位置中增加值 u
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
    }
}

// 初始化「树状数组」，要默认数组是从 1 开始
{
    for (int i = 0; i < n; i++) add(i + 1, nums[i]);
}

// 使用「树状数组」：
{   
    void update(int i, int val) {
        // 原有的值是 nums[i]，要使得修改为 val，需要增加 val - nums[i]
        add(i + 1, val - nums[i]); 
        nums[i] = val;
    }
    
    int sumRange(int l, int r) {
        return query(r + 1) - query(l);
    }
}

2.线段树「单点修改、区间修改、单点查询、区间查询->但性能不高」

参考资料：https://mp.weixin.qq.com/s/T3Ds8Eb8mZ5f96NjRFr6WA

以下笔记均参考力扣题解(推荐)：Range模块【线段树动态开点+线段树图解】

什么是线段树？

线段树其实是一种二叉搜索树，将一个大的区间划分为一个个单元区间。

内个单元区间表示成一个节点(单元区间->节点) 线段树中的线段，其实也是区间的意思，就是区间树

假设我们有一个数组为[1,2,3,4,5,6,7,8]，我们表示为一个区间和线段树就是下图：

可见线段树的区间是按照区间的中点进行分叉，左子节点的区间必定小于右子节点的区间，同理左右子树均是BST

构建线段树代码（val基于区间求和）：

/**
 * @author Fomalhaut
 * @date 2022/6/22
 * @desc 线段树模板(今天一定一定要写出来!!!!!)
 */
public class SegmentTree {
    // 用节点数组表示的线段树
    Node[] tree;
    // 原始数据
    int[] data;

    // 初始化线段树
    public SegmentTree(int[] data) {
        this.data = data;   // 载入数据
        this.tree = new Node[4 * data.length];  // 节点个数统一开4*N个
    }

    /*
        线段树节点类
         */
    static class Node {
        int left;   // (该节点对应的)区间左端点
        int right;  // 区间右端点
        int lazy;   // 懒标记
        int val;    // 节点值(根据不同的问题意义不同)
    }

    /*
    根据区间左右边界[l,r]来构建线段树:idx表示线段树的节点索引,l与r分别表示区间左右边界
     */
    public void build(int idx, int l, int r) {
        tree[idx] = new Node(); // 创建idx位置的节点
        tree[idx].left = l; // 该节点左边界为l
        tree[idx].right = r;    //该节点右边界为r
        // base case:到达叶子结点直接赋值
        if (l == r) {
            tree[idx].val = data[r - 1];    // 因为idx从1开始,区间的l与r也是从1开始,但是data索引从0开始,因此向左偏移1位
        }
        int mid = l + (r - l) / 2;  // [l,r]区间中点
        // 递归构建左右子树:当idx索引从1开始时,idx*2为左子节点,idx*2+1为右子节点
        build(idx * 2, l, mid); // 左子节点区间范围[l,mid] 左子节点个数>=右子节点
        build(idx * 2 + 1, mid + 1, r); // 右子节点区间范围[mid+1,r]
        tree[idx].val = tree[idx * 2].val + tree[idx * 2 + 1].val;  // 更新idx节点的值
    }
}

懒标记的引入：

如果是线段树，我们直接对根节点的值进行+(8-1+1)*1的操作就可以得到新的区间和，但是这样当我们查询中间某段区间的和时就会发现不对，因为这个+(8-1+1)*1没有涉及根节点的区间和操作！

于是就想可不可以在root处引入一个标记的量，在我们要下探到要求root子区间的区间和时可以把这个+1操作带下去？把子区间进行更新？于是就引入了lazy字段

注意： 我们只有在用到没有更新的区间时（也就是当前区间含有lazy），才会下传lazy，达到懒更新的目的。

也许我们还会更新[5,8]区间的值，我们除了设置lazy字段外，还需要将结果上传到他的父节点！（很显然，下面变了，上面区间包含下面也要变）

更新与查询代码如下（非动态开点）：

/*
更新某个区间的值:idx为节点索引,[l,r]为要更新的区间,val代表要更新进去的值
 */
public void update(int idx, int l, int r, int val) {
    // idx节点区间在要修改的[l,r]区间里面->直接更新到这里并并进行懒标记即可
    if (tree[idx].left >= l && tree[idx].right <= r) {
        // idx节点值 += val * idx节点区间的的节点数
        // 意思就是更新了idx节点的整个区间,节点值就加上相应的数
        tree[idx].val += (tree[idx].right - tree[idx].left + 1) * val;
        // 对idx节点进行懒标记
        tree[idx].lazy = val;
        return; // 结束
    }
    if (tree[idx].lazy != 0) pushDown(idx); // 当前节点有懒标记->下沉懒标记
    // [l,r]与idx节点左区间有交集
    if (l <= tree[idx * 2].right) update(idx * 2, l, r, val);
    // [l,r]与idx节点右区间有交集
    if (r >= tree[idx * 2 + 1].left) update(idx * 2 + 1, l, r, val);
    // 底下递归完成后向上回溯更新idx的值
    pushUp(idx);
}

/*
查询区间[l,r]
 */
public int query(int idx, int l, int r) {
    int res = 0;
    // idx节点的区间被[l,r]完全包含 -> 直接返回节点值
    if (tree[idx].left >= l && tree[idx].right <= r) return tree[idx].val;
    // 否则就还要继续往下走更小的区间
    // 遇到有懒标记也要下沉(因为你现在要查询小区间的信息)
    if (tree[idx].lazy != 0) pushDown(idx);
    // 跟左右区间有交集
    if (tree[idx * 2].right >= l) res += query(idx * 2, l, r);  // 累加递归完成的值
    if (tree[idx * 2 + 1].left <= r) res += query(idx * 2 + 1, l, r);
    return res; // 返回结果
}

/*
上传结果
 */
public void pushUp(int idx) {
    tree[idx].val = tree[idx * 2].val + tree[idx * 2 + 1].val;
}

/*
下沉懒标记
 */
public void pushDown(int idx) {
    // 向左右子节点下沉lazy(累加而不是覆盖)
    tree[idx * 2].lazy += tree[idx].lazy;
    tree[idx * 2 + 1].lazy += tree[idx].lazy;
    // idx节点区间的中点
    int mid = tree[idx].left + (tree[idx].right - tree[idx].left) / 2;
    // 左右子节点的节点值分别加上(懒标记的值*区间节点个数)
    tree[idx * 2].val += tree[idx].lazy * (mid - tree[idx].left + 1);
    tree[idx * 2 + 1].val += tree[idx].lazy * (tree[idx].right - mid);
    // 下沉了lazy后idx的懒标记置0
    tree[idx].lazy = 0;
}

动态开点的引入：

上述代码只是针对不对区间长度进行修改，只能在固定的区间内查询和修改，并且用到了4n的空间，有些空间根本没有被使用，有的题目数据规模到了1e9，如果我们开4n的空间并不可行！

于是我们需要动态地进行节点创建，即我们不用idx * 2和idx* 2 + 1来表示节点的左右子节点，而是在Node里添加leftChild和rightChild两个引用，来找到左右节点。由于我们是在更新与查询中进行动态开点，所以不需要build树！

动态开点的代码如下：

/**
 * @author Fomalhaut
 * @date 2022/6/23
 * @desc 线段树(动态开点+懒标记)
 */
public class SegmentTree_Dynamic {
    /*
    动态开点线段树节点类
     */
    static class Node {
        int left, right;    // 区间左右端点
        int val;    // 节点的值
        int lazy;   // 懒标记:0代表没有懒标记
        Node leftChild, rightChild; // 左右子树引用

        // 根据区间[left,right]创建节点
        public Node(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }

    /*
    动态开点的区间更新:root代表根节点,[l,r]代表更新区间,val代表更新的值
     */
    public void update(Node root, int l, int r, int val) {
        // 1.[l,r]不在root区间的范围内 -> 直接返回
        if (r < root.left || l > root.right) return;
        // 2.[l,r]包含root区间 -> 进行懒标记并更新root的值
        if (root.left >= l && root.right <= r) {
            root.lazy = val;    // 进行懒标记
            root.val += (root.right - root.left + 1) * val; // 节点值+=区间长度*val
            return;
        }
        // 3.继续往下走
        lazyCreate(root);   // 动态开点
        pushDown(root); // 下传lazy
        update(root.leftChild, l, r, val);  // 更新左子树区间
        update(root.rightChild, l, r, val); // 更新右子树区间
        pushUp(root);   // 上传结果
    }

    /*
    动态开点的查询区间[l,r]
     */
    public int query(Node root, int l, int r) {
        // [l,r]必定在root里面,因为root是最大的可能区间
        // 1.root的区间在[l,r]里面 -> 直接返回节点值
        if (root.left >= l && root.right <= r) return root.val;
        // 2.否则要往下走找到[l,r]完全包含子节点整个区间的情况
        lazyCreate(root);   // 动态开点
        pushDown(root); // 下传懒标记
        int mid = root.left + (root.right - root.left) / 2; // root区间中点
        // 左子树范围[ll, mid] 右子树范围[mid+1,rr]
        if (r <= mid) { // [l,r]只占据到root左子树
            return query(root.leftChild, l, r);
        } else if (l > mid) {   // [l,r]只占据到root右子树
            return query(root.rightChild, l, r);
        } else {    // [l,r]占据root左子树与右子树
            return query(root.leftChild, l, mid) + query(root.rightChild, mid + 1, r);
        }
        // 不用上传结果了因为查询不改变节点的值
    }

    /*
    上传结果
     */
    public void pushUp(Node root) {
        root.val = root.leftChild.val + root.rightChild.val;
    }

    /*
    下传懒标记:有懒标记->下传懒标记并更新子节点的值;没有->结束
     */
    public void pushDown(Node root) {
        // 当且仅当有懒标记才进行下传
        if (root.lazy != 0) {
            // 懒标记的值
            int v = root.lazy;
            // 懒标记下沉至左右子节点
            // 这里懒标记累加还是覆盖可以根据具体问题进行分析
            // 比如说是求区间的累加值就是+= 如果是只有两个状态那种可以直接进行覆盖(LC715.Range模块)
            root.leftChild.lazy += v;
            root.rightChild.lazy += v;
            // 更新左右子节点的值
            root.leftChild.val += (root.leftChild.right - root.leftChild.left + 1) * v;
            root.rightChild.val += (root.rightChild.right - root.rightChild.left + 1) * v;
            // root取消懒标记
            root.lazy = 0;
        }
    }

    /*
    创建左右子树
     */
    public void lazyCreate(Node root) {
        int mid = root.left + (root.right - root.left) / 2; // root区间中点
        // 创建左右子树并构建连接
        if (root.leftChild == null) root.leftChild = new Node(root.left, mid);
        if (root.rightChild == null) root.leftChild = new Node(mid + 1, root.right);
    }

数组表示的线段树(含懒标记+动态开点)可以参考三叶：

729. 我的日程安排表 I

package leetcode.SegmentTree;

import org.junit.Test;

/**
 * @author Fomalhaut
 * @date 2022/6/24
 * @desc 729. 我的日程安排表 I
 */
public class Q729 {
    @Test
    public void test() {
        MyCalendar myCalendar = new MyCalendar();
        System.out.println(myCalendar.book(10, 20));    // true
        System.out.println(myCalendar.book(15, 25));    // false
        System.out.println(myCalendar.book(20, 30));    // true
    }

    class MyCalendar {
        /*
        本题是线段树的模板题之一,由于值域范围在[0,1e9]因此只能采用动态开点的方式,否则会出现MLE
        本题要动态地获当前区间是否完全被覆盖,可以将线段树节点值设为当前区间的节点数(叶子结点只有0与1的区间和)
        同时为了使查询的时间复杂度为严格的O(logN)要加入懒标记
        ->查询[start,end)区间是否能book就相当于求[start,end-1]的区间和是否为0
        懒标记的线段树空间复杂度为O(MlogN),M为操作次数; 查询和更新一次时间复杂度为:O(logN)
         */

        /*
         节点类:
         本节点与之前的模板不同,该节点成员没有显式地包含节点u的区间左右端点[lc,rc]
         区间左右端点[lc,rc]可以通过update()与query()显式地传入再进行递归计算
         */
        class Node {
            // ls 与rs 分别代表当节点的左右子节点在tr中的下标 (相当于leftChild与rightChild)
            // val 表示当前节点的区间和(只有0与1)
            // add为懒标记
            int ls, rs, add, val;
        }

        int N = (int) 1e9, M = 120010, cnt = 1; // N 区间范围; M 节点个数; cnt 节点索引
        Node[] tr = new Node[M];    // 数组表示的线段树

        public MyCalendar() {
            tr[0] = new Node(); // 根节点u从tr[0]开始
        }

        /*
        更新[l,r]区间的节点,更新值为val=1
        u 根节点索引;lc 与 rc 代表根节点u表示的值域范围
         */
        public void update(int u, int lc, int rc, int l, int r, int val) {
            // 节点u表示的范围[lc,rc]在[l,r]内部 -> 直接更新节点值和懒标记
            if (lc >= l && rc <= r) {
                tr[u].val = (rc - lc + 1) * val;
                tr[u].add = val;
                return;
            }
            lazyCreate(u);  // 动态开点
            pushDown(u, rc - lc + 1);   // 下传懒标记
            // 递归更新左右子节点
            int mid = lc + (rc - lc) / 2;
            if (l <= mid) update(tr[u].ls, lc, mid, l, r, val); // [l,r]占据到左子树
            if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, val);  // [l,r]占据到右子树
            pushUp(u);  // 回溯更新u的值
        }

        /*
        查询[l,r]区间的节点
        u 根节点索引;lc 与 rc 代表根节点u表示的值域范围
         */
        public int query(int u, int lc, int rc, int l, int r) {
            if (lc >= l && rc <= r) return tr[u].val;   // u节点区间在[l,r]内
            // 否则继续往下走
            lazyCreate(u);  // 动态开点
            pushDown(u, rc - lc + 1); // 下传懒标记
            int mid = lc + (rc - lc) / 2, res = 0;
            if (l <= mid) res = query(tr[u].ls, lc, mid, l, r); // [l,r]占据到左子树
            if (r > mid) res += query(tr[u].rs, mid + 1, rc, l, r);  // [l,r]占据到右子树
            return res; // 返回左右区间总和
            // 查询不更新端点的值因此不用回溯
        }

        /*
        向上更新u的值
         */
        public void pushUp(int u) {
            tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
        }

        /*
        下传懒标记
        其中 len 为节点表示的区间长度 用于简化计算区间长度
         */
        public void pushDown(int u, int len) {
            int v = tr[u].add;
            if (v != 0) {   // 只有懒标记不为0才下传
                // 1.下传懒标记
                tr[tr[u].ls].add = v;
                tr[tr[u].rs].add = v;
                // 2.更新子节点的值(不判断懒标记就要+=避免0覆盖)
                tr[tr[u].ls].val = (len - len / 2) * v; // 左(大)
                tr[tr[u].rs].val = (len / 2) * v;   // 右(小)
                // 3.懒标记下传完置0
                tr[u].add = 0;
            }
        }

        /*
        动态开点:动按需态创建左右子节点并构建连接
         */
        public void lazyCreate(int u) {
            if (tr[u].ls == 0) {    // 当且仅当左子节点没有时才进行开点(tr[u].ls为0表示还没开左子节点)
                tr[u].ls = cnt++;   // 构建与tr[u]的连接,索引依次取
                tr[tr[u].ls] = new Node();  // 开点
            }
            if (tr[u].rs == 0) {
                tr[u].rs = cnt++;
                tr[tr[u].rs] = new Node();
            }
        }

        public boolean book(int start, int end) {
            // 区间[start,end-1]已经有东西填充过了->不能book
            if (query(0, 0, N, start, end - 1) > 0) {
                return false;
            }
            // 否则更新并返回true
            update(0, 0, N, start, end - 1, 1);
            return true;
        }
    }
}

731. 我的日程安排表 II(注意节点维护的是最大值)

package leetcode.SegmentTree;

import org.junit.Test;

/**
 * @author Fomalhaut
 * @date 2022/6/24
 * @desc 731. 我的日程安排表 II
 */
public class Q731 {
    @Test
    public void test() {
        MyCalendarTwo MyCalendar = new MyCalendarTwo();
        System.out.println(MyCalendar.book(10, 20));    // true
        System.out.println(MyCalendar.book(50, 60));    // true
        System.out.println(MyCalendar.book(10, 40));    // true
        System.out.println(MyCalendar.book(5, 15));     // false
        System.out.println(MyCalendar.book(5, 10));     // true
        System.out.println(MyCalendar.book(25, 55));    // true
    }

    class MyCalendarTwo {
        /*
        这题也可以用线段树进行求解:start与end的范围为[0,1e9]
        不过相比于Q729 我的日程安排表I 这里要维护的val为区间的最大值max
        当区间的最大值>=2就说明已经有两个重叠的预订,第3个预订就不能book了
        查询和更新一次时间复杂度为:O(logN) 空间复杂度为O(MlogN),M为操作次数
         */

        /*
        节点类
         */
        class Node {
            int ls, rs, add, max;   // ls, rs 为左右子节点在tr中索引(触手); add 懒标记; max 维护区间最大值
        }

        int N = (int) 1e9, M = 120010, cnt = 1; // N 区间范围; M 节点个数; cnt 节点在tr中的索引
        Node[] tr = new Node[M];

        public MyCalendarTwo() {
            tr[0] = new Node(); // 创建根节点
        }

        /*
        更新区间[l,r] 值为val
         */
        public void update(int u, int lc, int rc, int l, int r, int val) {
            // [l,r]在u表示的区间内
            if (lc >= l && rc <= r) {
                tr[u].add += val;   // 懒标记要累计(例如覆盖了2次)
                // 最大值是max(curVal,curVal+val)=curVal+val -> max += val;
                tr[u].max += val;
                return; // 结束
            }
            // [l,r]不在u内
            lazyCreate(u);  // 动态开点
            pushDown(u);    // 下传懒标记
            int mid = lc + (rc - lc) / 2;
            if (l <= mid) update(tr[u].ls, lc, mid, l, r, val); // 占据到左子树
            if (r > mid) update(tr[u].rs, mid + 1, rc, l, r, val);  // 占据到右子树
            pushUp(u);  // 回溯
        }

        /*
       查询区间[l,r]的最大值
         */
        public int query(int u, int lc, int rc, int l, int r) {
            if (lc >= l && rc <= r) return tr[u].max;
            lazyCreate(u);  // 冬天开点
            pushDown(u);    // 下传懒标记
            int mid = lc + (rc - lc) / 2, res = 0;
            if (l <= mid) res = query(tr[u].ls, lc, mid, l, r);
            if (r > mid) res = Math.max(res, query(tr[u].rs, mid + 1, rc, l, r));   // 记得取左右子节点的最大值
            return res; // 返回最大值
        }

        /*
        按需动态开点
         */
        public void lazyCreate(int u) {
            if (tr[u].ls == 0) {    // 左子节点不存在 -> 创建并构建连接
                tr[u].ls = cnt++;
                tr[tr[u].ls] = new Node();
            }
            if (tr[u].rs == 0) {
                tr[u].rs = cnt++;
                tr[tr[u].rs] = new Node();
            }
        }

        /*
        下传懒标记
         */
        public void pushDown(int u) {
            int v = tr[u].add;  // 节点u下传下来的懒标记
            if (v != 0) {   // 当且仅当懒标记不为0才进行下传
                // 下传懒标记至子节点(累计)
                tr[tr[u].ls].add += v;
                tr[tr[u].rs].add += v;
                // 更新左右子节点的值(累计)
                tr[tr[u].ls].max += v;
                tr[tr[u].rs].max += v;
                tr[u].add = 0;  // 下传懒标记完成撤销u的懒标记
            }
        }

        /*
        回溯更新u的最大值
         */
        public void pushUp(int u) {
            tr[u].max = Math.max(tr[tr[u].ls].max, tr[tr[u].rs].max);
        }

        public boolean book(int start, int end) {
            // 最大值>=2说明区间[start,end-1]存在某个点覆盖了2次
            if (query(0, 0, N, start, end - 1) >= 2) return false;
            update(0, 0, N, start, end - 1, 1);
            return true;
        }
    }
}

做完这两题估计对线段树有了充分了解了！

3.差分数组->「区间修改 & 单点查询」：

差分区间求和:将每个区间覆盖信息转化为变化量记录,最后从头开始统计变化量就可以将总的变化量求出来

比喻成公交车:上车就表示该时刻t1->新区间加入乘客+1；下车就表示区间结束->下一个时刻(t2+1)乘客-1

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        //  注意航班编号为1-n
        // 变化量计数器:索引[0,n-1]
        int[] counter = new int[n];
        // 遍历每个区间
        for (int[] booking : bookings) {
            // 因为航班编号为1-n,因此左偏移一位才是counter索引
            counter[booking[0] - 1] += booking[2];
            // 这里原本有+1又向左偏移一位就是原本的,要判断区间是否合法
            if(booking[1] < n) counter[booking[1]] -= booking[2];
        }
        // 该站人数=上一站人数+该站变化量
        // 注意最初的一站就是0+counter[0]=counter[0]
        for (int i = 1; i < n; i++) {
            counter[i] += counter[i - 1];
        }
        return counter;
    }
}