力扣1109. 航班预订统计差分入门模板题附线段树解法

本文主要是介绍力扣1109. 航班预订统计差分入门模板题附线段树解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题

本题属于「区间求和」问题中的入门难度。

差分解法：

class Solution {/*本题只涉及「区间修改 + 单点查询」，因此是一道「差分」的模板题。「差分」可以看做是求「前缀和」的逆向过程。对于一个「将区间[L,R]整体增加一个值 V」操作，我们可以对差分数组 C 的影响看成两部分：对 C[L]+=V：由于差分是前缀和的逆向过程，这个操作对于将来的查询而言，带来的影响是对于所有的下标大于等于L的位置都增加了值V；对 C[R+1]-=V：由于我们期望只对[L,R]产生影响，因此需要对下标大于R的位置进行减值操作，从而抵消“影响”。对于最后的构造答案，可看做是对每个下标做“单点查询”操作，只需要对差分数组求前缀和即可:
*/public int[] corpFlightBookings(int[][] bookings, int n) {int pre[]=new int[n+1],ans[]=new int[n]; //pre[]必须声明成n+1 因为C[R+1]-=V时R+1有可能越界了for (int[] booking : bookings) {int firsti=booking[0],lasti=booking[1],seatsi=booking[2];pre[firsti-1]+=seatsi;pre[lasti]-=seatsi;}ans[0]=pre[0];for (int i = 1; i < n; i++) {ans[i]=ans[i-1]+pre[i];}return ans;}
}

线段树可以无脑解决所有的「区间求和」问题，但是很多时候没必要，代码量太大，表现也不是最好的：

class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {for (int[] booking : bookings) {int l=booking[0]-1,r=booking[1]-1,seatsi=booking[2];update(root,0,n,l,r,seatsi);}int ans[] = new int[n];for (int i = 0; i < n; i++) {ans[i]=query(root,0,n,i,i);}return ans;}class Node {Node left, right;int val, add;}private int N = (int) 2e4;//线段树范围大小private Node root = new Node();// 在区间 [start, end] 中更新区间 [l, r] 的值，将区间 [l, r] ➕ val// 如果结点表示为「区间最值」的情况时在更新结点时不需要✖️叶子节点的数量// 下面的pushDown函数里也是 也要根据题目判断是否需要✖️叶子节点的数量// 如果是「点更新」 也不需要✖️叶子节点的数量  因为此时区间是一个点所以一定会更新到叶子节点//start, end一般是用0和N 对应root的范围！public void update(Node node, int start, int end, int l, int r, int val) {if (l <= start && end <= r) {node.val += (end - start + 1) * val;//✖️叶子节点的数量node.add += val;//这里俩个+=如果在点赋值时可以改成= 点累加不行return ;}int mid = (start + end) >> 1;pushDown(node, mid - start + 1, end - mid);if (l <= mid) update(node.left, start, mid, l, r, val);if (r > mid) update(node.right, mid + 1, end, l, r, val);pushUp(node);}// 在区间 [start, end] 中查询区间 [l, r] 的结果， [l ,r] 保持不变public int query(Node node, int start, int end, int l, int r) {if (l <= start && end <= r) return node.val;int mid = (start + end) >> 1, ans = 0;pushDown(node, mid - start + 1, end - mid);if (l <= mid) ans += query(node.left, start, mid, l, r);if (r > mid) ans += query(node.right, mid + 1, end, l, r);return ans;}// 向上更新private void pushUp(Node node) {node.val = node.left.val + node.right.val;}// 推懒惰标记的函数// 如果是「覆盖」的更新操作 则在下推懒惰标记的时候『不需要累加』private void pushDown(Node node, int leftNum, int rightNum) {if (node.left == null) node.left = new Node();if (node.right == null) node.right = new Node();if (node.add == 0) return ;// 当前节点加上标记值✖️该子树所有叶子节点的数量 同上面update函数同步修改node.left.val += node.add * leftNum;node.right.val += node.add * rightNum;//这里俩个+=如果在点赋值时可以改成= 点累加不行// 对区间进行「加减」的更新操作时，下推懒惰标记时需要累加起来，不能直接覆盖node.left.add += node.add;node.right.add += node.add;node.add = 0;}
}