刷算法题的人应该都遇到过这种场景给一个数组动不动就要改某个位置的值然后问你某个区间和是多少。我第一次遇到这个问题时第一反应是前缀和数组结果一引入修改操作就彻底抓瞎了每一次改值都得重新算一堆前缀和复杂度直接起飞。后来在学长推荐下学了树状数组才明白这种单点修改 区间查询的场景原来可以做到 O(log n) 的时间复杂度而且代码短得离谱。之后又啃了不少树状数组的练习题慢慢发现这东西根本不是只会一个模板就够了的lowbit 背后的二进制拆分思想、差分扩展、权值树状数组、二维树状数组每一样都在不同题型里卡出过新高度。这篇东西我打算按自己的学习路径来写先把树状数组为什么会出现、lowbit 为什么是灵魂讲透然后直接给一套能抄走的树状数组模板接着讲怎么用差分把它从单点修改扩成区间修改最后拆几道典型的练习题把逆序对、离散化、第 k 小、二维 BIT 这些高频套路完整过一遍。适合刚学完基础数据结构、准备刷题的人也适合那些会用模板但从没真正搞懂原理的同学。放心全程不搞虚的全部围绕怎么落地、怎么避开我踩过的那些坑来讲。1. 动态前缀和这道坎树状数组为什么会出现树状数组这名字听着挺高大上其实它解决的就是一个非常朴素的问题动态维护前缀和。什么叫动态就是数组的值会变。如果数组是静态的那一个前缀和数组 pre[i] pre[i-1] a[i] 就搞定了O(1) 查询怎么想怎么舒服。可题目一旦加上修改操作事情就变味了。1.1 暴力做法的瓶颈为什么普通前缀和数组带不动修改先看最直接的暴力方案每次修改 a[i]就直接改原数组查询 [l, r] 的时候从 l 到 r 循环累加。这个方案修改是 O(1) 的但查询是 O(n) 的。当操作次数 m 和数据规模 n 都达到 10^5 甚至 10^6 时O(n*m) 就是 10^10 这个量级基本等于宣判死刑。再看静态前缀和方案查询是 O(1) 了但每次修改 a[i]都得把 pre[i] 到 pre[n] 全部重新计算最坏 O(n)。同样n 和 m 一大还是死。这就是树状数组要解决的核心矛盾查询希望预计算的信息越多越好这样查询时才能快速得出答案修改希望受影响的信息越少越好这样每次改值别牵扯一大片。这两种诉求天然冲突。如果你想要一个数据结构同时把两个操作都压到 O(log n)就必须放弃完整前缀和这种过于整齐的预处理方式改成分层维护若干个块。树状数组就是这种思路里最优雅的一个实现。1.2 从静态前缀和到动态维护折中方案的分块思想为什么我不一开始就讲树状数组的代码因为如果不懂它到底在干嘛模板背得再熟也只会生搬硬套。树状数组本质上就是一种分段前缀和它不预处理所有前缀而是每个下标 x 只维护一个区间(x - lowbit(x), x]的和。举个例子c[8] 存的是 a[1] 到 a[8] 这 8 个数的和c[6] 存的是 a[5] 到 a[6] 这 2 个数的和c[7] 只存 a[7] 这一个数的和。也就是说不同的下标管理不同大小的管辖区间而这些区间长度全都是 2 的整数次幂。这样一来查询前缀和就变成了拼图把若干段长度为 2 次幂的已知区间拼起来恰好覆盖 [1, x]。修改某个单点时只需要更新那些管辖范围恰好覆盖了这个点的 c 数组位置。两种操作的时间都取决于区间拆分的数量而这个数量被二进制性质限制在 O(log n) 以内。这个思路其实和跳表有点像——不追求一步到位而是用跳跃换取效率。我后面讲 lowbit 的时候你会发现这个跳跃路径特别有规律根本不涉及什么复杂的递归或平衡树维护。1.3 树状数组与线段树的定位差异选型不是越强越好很多人学完线段树后就会产生一个疑问树状数组能做的线段树都能做那我为什么还要学树状数组确实线段树能处理区间修改、区间查询、区间最值等各种花活功能上完全碾压树状数组。但问题是杀鸡焉用牛刀。线段树的代码量摆在那里建树、pushup、pushdown、update、query全套写下来七八十行是家常便饭还得小心递归边界。而树状数组的核心操作就两个函数加起来不到二十行。再看常数线段树由于递归调用和节点访问的模式实际运行时间往往比树状数组大一个档次。在某些卡时间的题目里线段树能被树状数组快出一两倍甚至是量级的差距。我自己的选型经验是这样一个优先级只涉及单点修改 区间和查询无脑树状数组涉及区间修改 区间查询先用差分转换思路能转成单点就用树状数组转不了再考虑线段树涉及区间最值、区间赋值、区间取反这类需要合并和懒标记的操作直接用线段树别在树状数组上硬凹。说白了数据结构不是越高级越好而是在满足需求的前提下越简单越好。2. lowbit 是灵魂树状数组的二进制骨架前面我提到了 lowbit但没有细讲。现在必须把这个词彻底掰开揉碎因为不会 lowbit树状数组就只是一堆莫名其妙的加加减减理解了 lowbit整个树状数组就是一个顺理成章的二进制结构。2.1 一个下标 x 到底管了哪些元素lowbit(x) 的定义是x 的二进制表示中最低位的 1 所代表的值。比如 x 5 时二进制是 101最低位的 1 对应 1所以 lowbit(5) 1x 6 时二进制是 110最低位 1 对应 2所以 lowbit(6) 2x 8 时二进制是 1000最低位 1 对应 8所以 lowbit(8) 8。代码实现一句话lowbit(x) x -x。原理不复杂正数的相反数在计算机里用补码表示等于按位取反再加一这样 x 和 -x 按位与的结果恰好保留下 x 的最低一个 1。那这个 lowbit 和管辖区间有什么关系关系大了。树状数组的 c[x] 存的就是区间(x - lowbit(x), x]的和。下表列几个位置看完就清晰了下标 xx 的二进制lowbit(x)c[x] 管辖的区间100011(0,1]即 a[1]200102(0,2]即 a[1]..a[2]300111(2,3]即 a[3]401004(0,4]即 a[1]..a[4]501011(4,5]即 a[5]601102(4,6]即 a[5]..a[6]701111(6,7]即 a[7]810008(0,8]即 a[1]..a[8]注意观察规律下标是奇数时lowbit 一定是 1所以奇数位置只管自己下标是 2 的整数次幂时它管的是从 1 到自己的全部前缀。这也就是为什么树状数组下标一般从 1 开始——从 0 开始会让整个结构和这个划分方式完全错位。2.2 查询前缀和每次减去 lowbit 的跳跃逻辑假设我想查询 sum(7)也就是 a[1] 到 a[7] 的和。如果直接用 c 数组怎么拼第一步看 c[7]它管的是 (6,7]也就是 a[7] 一个数取值得到 a[7] 第二步跳到下标 6即7 - lowbit(7) 6。c[6] 管的是 (4,6]也就是 a[5]..a[6]取值 第三步跳到下标 4即6 - lowbit(6) 4。c[4] 管的是 (0,4]也就是 a[1]..a[4]取值 第四步跳到 0结束。把三次的 c 加起来c[7] c[6] c[4]覆盖的区间分别是 [7,7]、[5,6]、[1,4]正好无缝拼成 [1,7]。神奇吧它就像二进制拆数7 4 2 1对应的区间长度也正好是 4、2、1。这个规律不是巧合任何正整数 x 都能拆成若干个 2 的幂之和而树状数组就是按这个幂次把整个前缀切成了对应的小段。所以查询代码其实就是一个 while 循环int sum(int i) { int res 0; while (i 0) { res c[i]; i - lowbit(i); } return res; }每一轮 i 的低位 1 都会被消掉循环次数等于 i 二进制中 1 的个数最坏情况下不超过 O(log n)。这就是树状数组查询快的根源。2.3 更新单点反向加上 lowbit 向上传播查询是向下跳更新则是向上跳。假设要给 a[3] 加上 v那么所有管辖范围覆盖下标 3 的 c 位置都要变。哪些位置覆盖了 3看图说话c[3]管 [3,3]、c[4]管 [1,4]、c[8]管 [1,8]……总之往上走。从 3 出发下一步是3 lowbit(3) 4再下一步是4 lowbit(4) 8再下一步是8 lowbit(8) 16……一路加到超过 n 为止。void add(int i, int v) { while (i n) { c[i] v; i lowbit(i); } }这里的直觉是包含 a[i] 的 c 数组位置只可能出现在向上不断加 lowbit这条路径上。因为 c[x] 管辖的范围是(x - lowbit(x), x]如果i在某个 c[x] 的范围内那么 x 和 i 的最低位 1 位置一定存在严格的包含关系而 add 的跳法恰好能全部走到。这组镜像操作——query 减 lowbit、update 加 lowbit——就是树状数组的全部秘密。你不需要把整棵树画出来只要记住查询向左上拼区间、更新向右上爬路径写代码时就不会晕。3. 可以直接抄走的树状数组模板写法、细节和易错点光懂原理还不行得能写对。我见过太多人原理说得头头是道一写代码就出各种匪夷所思的 bug。这一节我不光给模板还把每个细节的为什么讲明白把坑提前指出来。3.1 单点更新 区间查询的基础模板直接用 C14 写注释我会给全#include bits/stdc.h using namespace std; const int N 100005; int n; // 数组大小 int a[N]; // 原数组如果需要初始化 int bit[N]; // 树状数组 int lowbit(int x) { return x -x; } // 单点修改a[i] v void add(int i, int v) { while (i n) { bit[i] v; i lowbit(i); } } // 前缀和sum(a[1..i]) long long query(int i) { long long res 0; while (i 0) { res bit[i]; i - lowbit(i); } return res; } // 区间和sum(a[l..r]) long long range_query(int l, int r) { return query(r) - query(l - 1); }用的时候注意bit数组初始全零然后对每个位置 i 调用add(i, a[i])完成初始化。之后的单点加、区间求和就直接调用add和range_query就行。如果题目每次操作是把 a[pos] 改成 x那就先算差值再add(pos, x - a[pos])别搞错了。这个模板还有一个隐藏细节query的返回类型我用了long long。虽然单个 c[x] 存的是 int 范围的数据但前缀和的累加结果很容易超过 int 上限。在算法竞赛里区间求和题我从来默认用 long long不然经常在某个边界数据上爆掉排查起来非常痛苦。3.2 初始化建树三种方式及各自场景第一种也是我开头说的逐个add复杂度 O(n log n)。代码最简单逻辑最清晰适合大部分场景。数据量在 10^6 以内基本没问题。第二种O(n) 直接建树。思路是先将 bit[i] 初始化为 a[i]然后利用父节点累加子节点的方式推出所有值代码也不复杂for (int i 1; i n; i) { bit[i] a[i]; int j i lowbit(i); if (j n) bit[j] bit[i]; }这个 O(n) 建树的原理其实就是把 add 过程中的每个节点只向父节点贡献一次给显式展开了。它不能减少代码复杂度但能少掉 O(log n) 的初始化开销。当数据量达到 10^7 这个量级时初始化时间差异还是很明显的不过平时做题其实用不太上跟第一种的差别通常可以忽略。第三种是差分建树适用于后面要讲的区间更新场景。三种方式的选择我一般这样判断单测数据、n 在 10^6 以内直接用最简单的一一 add多测数据总量很大用 O(n) 建树需要用差分 BIT 处理区间更新就按差分公式来。不用为了几毫秒纠结先把最简单、最不容易写错的方式练熟。3.3 三个我踩得比较深的坑第一个坑下标从 1 开始不是矫情。很多人习惯数组从 0 开始拿到树状数组模板也下意识从 0 开始建结果 add(0, v) 的时候i lowbit(i)lowbit(0) 0i 永远不变死循环到天荒地老。我的习惯是读入时直接存到 a[1..n]所有 BIT 操作以下标 1 为基准这样就不会踩坑。第二个坑数组开多大。BIT 数组大小不是 n而是 n1注意有些操作会访问到 n1。比如差分做区间更新时如果对 [l, r] 做加法要在 r1 处减掉 v当 r n 时add(n1, -v)就会越界。所以差分场景建议把 bit 开到 n2宁多勿少。第三个坑多组测试数据忘记清空。树状数组的初始化是从全零开始然后 add如果上一组数据还有残留值这一组就全乱了。多测时别偷懒memset(bit, 0, sizeof(bit))是一定要写的。如果你用的是动态分配也记得重新 fill。还有一个小细节有同学会把二分的 mid 跟树状数组混在一起导致 bit 更新时用错了坐标。建议所有 BIT 操作里都只用数组下标这一个概念函数内部不做什么映射这样最不容易错。4. 从单点到区间差分技巧把树状数组扩出一倍战斗力基础树状数组只能单点修改、区间查询。但很多题目的操作是把区间 [l, r] 的每个元素都加上 v这种时候直接用基础 BIT 就会非常尴尬。好在有一个经典套路——差分数组它可以把区间修改转化成两个单点修改让树状数组瞬间升级。4.1 区间更新 单点查询一阶差分树状数组差分数组定义很简单d[i] a[i] - a[i-1]约定 a[0] 0。想一想如果对 a[l..r] 每个数都 v那么差分数组 d 里发生了什么d[l] a[l] - a[l-1]a[l] 加了 va[l-1] 没加所以 d[l] 多了 vd[r1] a[r1] - a[r]a[r1] 没加a[r] 加了 v所以 d[r1] 少了 v区间内部的 d 值前后两个 a 都加了 v差值不变。结论就是区间加 v 的操作等价于在差分数组上做两个单点修改——d[l] v; d[r1] - v。然后看单点查询想算出当前的 a[i]只需要对 d 做前缀和即a[i] d[1] d[2] ... d[i]。这不就是树状数组最拿手的 prefix sum 吗所以这个场景的完整套路是// 区间 [l, r] v add(l, v); add(r 1, -v); // 查询当前 a[pos] query(pos);差分思想的核心就是把对一整个连续的区间做操作化为对两个端点做操作。这种端点化思路在算法里很常见比如扫描线、莫队都隐约有类似的味道。想通了这一层你再看很多区间修改题目就会自然而然往差分方向靠。4.2 区间更新 区间查询二阶差分是怎么推出来的区间更新 区间查询是更常见的组合操作比如把 [l, r] 的每个数加 v然后问 [l, r] 的和。一阶差分解决了更新问题但查询变成了求 a 的前缀和也就是 d 的二阶前缀和没法直接用单个 BIT 搞定。这里需要一点数学推导。设差分数组为 d那么a[1] a[2] ... a[x] Σ(i1..x) Σ(j1..i) d[j]交换求和次序就是考察每个 d[j] 在前缀和公式里被加了几次Σ(j1..x) d[j] * (x - j 1)拆开这个式子(x 1) * Σ d[j] - Σ (j * d[j])也就是说只要同时维护两个树状数组一个存 d[i]一个存 i * d[i]就能 O(log n) 地算出任意前缀和void range_add(int l, int r, long long v) { add(bit1, l, v); add(bit1, r 1, -v); add(bit2, l, l * v); add(bit2, r 1, -(r 1) * v); } long long prefix_sum(int x) { return (x 1) * query(bit1, x) - query(bit2, x); } long long range_sum(int l, int r) { return prefix_sum(r) - prefix_sum(l - 1); }这里的add和query都是前面模板里的函数只是多了个维护哪个 BIT的参数而已。看起来维护两个数组有点绕但原理其实就是用两个 BIT 分别缓存公式里的两项。推导过程虽然简单但第一次见的人往往一脸问号——建议亲手在纸上把式子展开一遍印象会很深。4.3 什么题目适合直接上差分 BIT不是所有区间修改都值得上差分我根据自己的刷题经验整理了几类典型区间统一加/减一个值最后查询单点值一阶差分最经典区间统一加/减一个值中间穿插区间求和二阶差分区间赋值、区间翻转差分帮不上忙直接线段树。判断标准很简单操作是否可以用两个端点的相加等价表示。凡是能就尽量往差分 BIT 上靠。凡是不能别硬套。5. 练习题拆解五道高频题型背后的统一套路树状数组太理论了不行必须落到题目上。下面这五类题是我觉得覆盖了树状数组大部分应用场景的经典体型每道我都会把破题思路讲透并标出那个最关键、最容易被卡住的点。5.1 逆序对把树状数组当桶用题目问给定一个数组有多少对 (i, j) 满足 i j 且 a[i] a[j]这是树状数组最经典的应用之一。核心思路是把值当成位置把树状数组当成桶来用。从后往前扫描数组每遇到一个数 a[i]先去树状数组里查询已经扫描过的、比 a[i] 小的数的个数即query(a[i] - 1)因为这个数是当前数右边的数所以比当前数小的右边元素个数就是在以当前数为左端点时的逆序对数量然后add(a[i], 1)把这个数也放进桶里。最终答案就是query(a[i] - 1)的累加。long long ans 0; for (int i n; i 1; --i) { ans query(a[i] - 1); add(a[i], 1); }这里的树状数组装的不是原数组的值而是某个数值出现了多少次。所以树状数组不只可以求区间和本质上它更适合做值域上的统计。这个迁移思维很重要因为权值树状数组、求第 k 小、求众数区间等问题全都是基于这个思维的。5.2 离散化细节值域大时怎么处理逆序对的经典坑在于a[i] 的取值范围可以到 10^9但数组长度 n 只有 10^5。直接开一个 10^9 的 BIT 数组内存直接爆掉。所以需要离散化把所有出现过的数值排序去重然后用它们在有序数组中的排名来代表原值。离散化的标准三步复制一份数组 b a排序b.erase(unique(b.begin(), b.end()), b.end())去重对每个 a[i]用lower_bound(b.begin(), b.end(), a[i]) - b.begin() 1得到它的离散化排名。这里有个常见 bug忘记去重。如果不 unique两个相同的值会占据两个排名那么后续统计大于当前值的个数就会出错。我一开始就栽在这个上面后来学乖了写离散化必带一句 unique不然后患无穷。另一个小经验离散化后的 BIT 大小设为去重之后的元素个数 m而不是原数组长度 n。虽然 m ≤ n但两者可能差很多用 n 也没错但省点内存总是好的。5.3 求第 k 小元素权值树状数组的基座权值树状数组还有一个威力巨大的操作在 O(log n) 时间内找到当前所有已插入元素中第 k 小的值。这背后依赖的是树状数组天然的二进制结构。思路是从高位到低位尝试。我们可以把树状数组的累加路径看成一个二进制数字的构建过程先尝试一个大的步长如果步长对应的前缀和小于 k就保留这个步长并继续否则缩小步长再试。int find_kth(int k) { int pos 0; // 假设 BIT 大小 n且 n 是 2 的幂级别的值 for (int step highest_power_of_two; step 0; step 1) { int nxt pos step; if (nxt n bit[nxt] k) { pos nxt; k - bit[nxt]; } } return pos 1; }这个find_kth的本质是在树状数组的节点上做二进制倍增。它和二分答案 query(mid) 的做法相比省掉了每次二分都要重新调用 query 的 O(log n)直接把复杂度压到一次 O(log n)。当 n 10^5、操作次数 10^5 时这个优化还是相当可观的。我第一次写这个函数时老觉得步长和位置之间的关系很玄后来想通了个关键树状数组的 c[pos step] 正好是从 pos1 到 posstep 这段区间的和因为树状数组的节点下标天然构成了一个二进制分组。所以每走一步都相当于吞掉了一段连续区间最后停在的位置就是第 k 小元素所在位置。5.4 二维树状数组单点修改 子矩阵查询二维 BIT 是入门树状数组之后很自然的扩展适合处理单点修改 子矩阵和查询这类问题。原理就是把一维 BIT 的每个节点再挂一个一维 BIT。原本 c[x] 管理一段 x 区间现在是 c[x][y] 管理一个x 方向的区间和 y 方向的区间交错形成的矩形。代码也非常对称void add2(int x, int y, int v) { for (int i x; i n; i lowbit(i)) for (int j y; j m; j lowbit(j)) bit[i][j] v; } long long query2(int x, int y) { long long res 0; for (int i x; i 0; i - lowbit(i)) for (int j y; j 0; j - lowbit(j)) res bit[i][j]; return res; } // 子矩阵 [(x1,y1),(x2,y2)] 的和 long long range_query2(int x1, int y1, int x2, int y2) { return query2(x2, y2) - query2(x1 - 1, y2) - query2(x2, y1 - 1) query2(x1 - 1, y1 - 1); }子矩阵查询的容斥公式和二维前缀和完全一样加右上、减左上、减右下、加左下。二维 BIT 的复杂度是 O(log n * log m)因为两层循环各跳一次 lowbit。需要注意的是二维 BIT 不太适合区间修改 区间查询因为差分公式会展开成四组还要维护四个 BIT代码量大且容易乱。如果你真遇到二维区间更新的题我建议直接考虑二维线段树或者树状数组的差分扩展不要在二维 BIT 的原始形态上硬套。5.5 树状数组维护区间最值有条件但很实用的技巧很多人以为 BIT 只能维护和其实它也能维护最大值只是有限制它天然支持的是单点变大 前缀最大值查询。什么意思就是说你在做add(i, val)时如果 val 比 bit[i] 更大才更新 bit[i]查询query(i)时取的是 [1, i] 范围内的最大值而不是和。void update_max(int i, int val) { while (i n) { if (val bit[i]) bit[i] val; i lowbit(i); } } int query_max(int i) { int res 0; while (i 0) { res max(res, bit[i]); i - lowbit(i); } return res; }这套东西在动态求前缀最大值、且修改只会让值变大的题目里非常好用典型场景比如股票交易里的之前某天的最大收益。但要注意它无法处理区间任意子区间的最值查询也无法处理把最大值改小这种会破坏信息的操作因为 c[x] 里的 max 一旦变大就无法撤销。我一再强调这个单向条件是因为见过很多同学把 BIT 的最值当线段树用结果遇到把 a[i] 改小的题目直接 WA 到晕厥。区间任意最值老老实实线段树别跟 BIT 过不去。6. 实战之后才明白的几个道理性能、调参与取舍写到这里模板和题目都过了一遍最后聊点实战中积累的私货。这些经验不是某个算法书会专门讲的但全是我自己踩过坑之后体会最深的。6.1 树状数组的实际常数优势有多大很多人对比复杂度只看 O(log n) 和 O(log n) 相等就觉得树状数组和线段树差不多。实际上线段树是递归实现每次操作都有函数调用、参数传递、栈帧切换的开销BIT 就是个 while 循环中间还涉及大量连续内存访问。放在同一份数据上跑BIT 往往明显更快。我在 10^6 规模的数组上做过粗略测试同样是 10^6 次操作线段树比 BIT 慢大约 30% 到 100%这差距在卡时限的题里可能就是 AC 和 TLE 的区别。还有内存。线段树要开 4n 的空间BIT 只要 n最多 n2在内存限制 64MB 的题目里这个差距能直接影响你能不能用线段树。所以我遇到单点修改 区间查询的题第一选择永远是 BIT不是因为它更高级恰恰是因为它更省、更快、更简单。6.2 调试技巧写个暴力对拍比什么都快树状数组的 bug 有个特点样例过了不代表你对了边界数据能把你炸得渣都不剩。我的习惯是每次写完 BIT 代码如果时间充裕一定写一个小型暴力程序去对拍。对拍结构其实很固定随机生成 n 和 m随机生成初始数组和操作序列暴力程序直接模拟输出答案BIT 程序也输出答案两者对比不一致就输出当前数据方便定位。我写过一个简单对拍脚本每次随机数据量不大n ≤ 20m ≤ 50但能覆盖大量边界情况。这个习惯帮我抓出过很多隐蔽的问题比如下标从 1 开始但读入时忘了 1、离散化后 BIT 范围设置偏小等等。另一个很有效的调试手段是打印 BIT 的访问路径。在 add 和 query 函数里临时加一行cerr i 看它从哪个下标跳到哪个下标能快速判断是不是 lowbit 写错了。这种细节肉眼很难看出来打出来一瞬间就清楚了。6.3 什么场景下别用树状数组虽然我觉得 BIT 好用但它不是万能的。总结下我劝退 BIT 的几种情况需要区间赋值、区间取反这类的操作这类操作往往需要懒标记和区间整体更新BIT 的信息组织方式根本做不了需要任意区间最值且修改非单调BIT 的前缀最大值方案存在致命缺陷老老实实线段树需要区间查询且同时支持区间修改但差分无法表达操作语义例如把区间内所有元素变成它的平方差分表达式写不出来别强求二维甚至三维区间问题BIT 可以二维但维护起来内存和复杂度都在涨先评估线段树的方案。最后的最后分享一个我自己总结的小方法论数据结构题目最忌讳上来就套模板。先想明白操作的本质再看能不能转换成单点修改 前缀查询这个 BIT 最擅长的模式。能转换就用 BIT不能再看线段树。这个思考路径几乎可以应对 90% 以上的树状数组练习题也让我从最初背模板背到怀疑人生的状态慢慢变成看到一个题就能大致判断需要什么结构。数据结构的乐趣不在模板本身而在拆解问题的那个过程。