1前缀和回顾
a=1 2 3 4，s[3] 是多少？a[2..4] 是多少？
算法进阶 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2前缀和的难题
修改 a[2] 后，前缀和数组需要更新哪些位置？
3lowbit 直觉
lowbit(8)？lowbit(20)？
4lowbit 计算
手算 6 & (-6)（按 4 位补码）。
5树状数组结构
c[8] 管 a 的哪一段？c[7] 呢？
6单点修改
n=8 时，add(3,…) 会依次更新哪些下标？
7前缀求和
sum(7) 会累加哪些 c？
8单点改区间查
用 sum 表示 a[3..7] 的和。
9区间改单点查
对 [2,4] 加 5，需要做哪两次 add？
10逆序对
序列 3 1 2 有几个逆序对？
第 1 页 · 背面（答案）
参考答案（家长）：s[2],s[3],…,s[n] 全部，共 n-1 个。
参考答案（家长）：s[3]=6；a[2..4]=s[4]-s[1]=10-1=9。
参考答案（家长）：6=0110，-6=1010，与后 =0010=2。
参考答案（家长）：8=1000→8；20=10100→4。
参考答案（家长）：3→4→8。
参考答案（家长）：c[8] 管 a[1..8]；c[7] 管 a[7..7]。
参考答案（家长）：sum(7)-sum(2)。
参考答案（家长）：c[7]+c[6]+c[4]（7→6→4→0）。
参考答案（家长）：(3,1)、(3,2) 共 2 个。
参考答案（家长）：add(2,5) 和 add(5,-5)。
第 2 页 · 正面（题目）
11线段树·登场
区间最大值能像树状数组那样用“前缀差”求出来吗？
12线段树·结构
[1,4] 的根往下分成哪两个子区间？
13线段树·存储
节点 5 的两个孩子编号是多少？
14线段树·建树
一棵管理 8 个数的线段树，根节点管的是哪几个数？
15线段树·上传
若线段树维护区间最小值，pushup 该怎么写？
16线段树·单点改
改一个叶子，一共要更新几个节点？
17线段树·查询思路
若当前节点区间与查询区间完全无交，该怎么办？
18线段树·区间和
为什么"完全落在区间内"时可以直接返回，不用再往下递归？
19线段树·区间最值
求区间最大值时，无交节点应返回什么？
20线段树·懒标记直觉
打了懒标记的节点，它的孩子此刻是最新的吗？
第 2 页 · 背面（答案）
参考答案（家长）：[1,2] 和 [3,4]。
参考答案（家长）：不能，最大值不能相减还原。
参考答案（家长）：全部 8 个。根管整个区间，往下每层对半分。
参考答案（家长）：10 和 11。
参考答案（家长）：从叶子到根这一条链上的所有节点，约 log n 个。
参考答案（家长）：tr[p]=min(tr[2p],tr[2p+1])。
参考答案（家长）：这个节点的值已经是这段区间的和了，往下拆只会重复计算。
参考答案（家长）：直接返回（求和取 0，求最大值取极小）。
参考答案（家长）：不一定，修改被“欠”在标记里，用到时才下放。
参考答案（家长）：一个极小值（如 INT_MIN），不影响 max。
第 3 页 · 正面（题目）
21线段树·下放
下放后父节点的懒标记应变成什么？
22线段树·区间改
递归进入孩子之前必须先做什么？
23单调栈·直觉
要找“右边第一个更大”，栈里应保持递增还是递减？
24下一个更大
序列 2 1 3，元素 1 的下一个更大（值）是谁？
25单调栈·复杂度
n 个元素，单调栈总的入栈加出栈操作数量级是多少？
26单调栈·应用
柱状图求最大矩形，对每根柱子要找它左右第一个“更矮”还是“更高”？
27单调队列·直觉
求窗口最大值，队列里下标对应的值应保持怎样的单调性？
28滑动窗口最值
判断队首过期的条件是什么？
29单调队列·实现
队列里存下标还是存值更方便判断过期？
30单调队列·应用
求窗口最小值时，队尾应弹出哪些元素？
第 3 页 · 背面（答案）
参考答案（家长）：pushdown（下放懒标记）。
参考答案（家长）：清零（已交给孩子）。
（无答案）
参考答案（家长）：递减（从栈底到栈顶递减），遇到更大就弹出结算。
参考答案（家长）：更矮（矮柱之间才是它能延伸的宽度）。
参考答案（家长）：O(n)。
参考答案（家长）：q.front()<=i-k。
参考答案（家长）：单调递减（队首最大）。
参考答案（家长）：弹出 >=a[i] 的（保持队列递增）。
参考答案（家长）：存下标（可直接比较位置）。