树状数组（Binary Indexed Tree）—— 优雅的前缀和利器它能做什么？树状数组（Fenwick Tree）在 $O(\log n)$ 时间内支持：单点修改：add(i, x) — 位置 i 加上 x前缀查询：sum(i) — 查询 $[1, i]$ 的区间和区间和 $[l, r] = sum(r) - sum(l-1)$，一次减法搞定。相比线段树：代码短、常数小；代价是只支持可逆操作（加法、异或等），不支持区间最值。核心思想：lowbit树状数组的基石是 lowbit —— 取一个数二进制最低位的 1：lowbit(x) = x & -xx二进制lowbit100011200102300111401004501011601102701111810008lowbit 的几何直觉每个下标管辖一段区间，长度 = lowbit(i)：下标: 1 2 3 4 5 6 7 8 [1] [ ] [3] [ ] [5] [ ] [7] [ ] [1---2] [1-----------4] [1---------------------------8]tree[1] 管 $[1, 1]$（长度 $lowbit(1)=1$）tree[2] 管 $[1, 2]$（长度 $lowbit(2)=2$）tree[3] 管 $[3, 3]$（长度 $lowbit(3)=1$）tree[4] 管 $[1, 4]$（长度 $lowbit(4)=4$）tree[8] 管 $[1, 8]$（长度 $lowbit(8)=8$）树形结构 8 ┌───────┴───────┐ 4 12 ┌───┴───┐ ┌───┴───┐ 2 6 10 14 ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ 1 3 5 7 9 11 13 15i 的父亲 = i + lowbit(i)，这正是 add 向上更新的路径。add 函数：向上更新修改位置 i，然后一路跳到父亲，直到超出范围。i → i + lowbit(i) → i + lowbit(i) + lowbit(...) → ...// 位置 i 加上 x（1‑based） void add(int i, int x) { while (i <= n) { tree[i] += x; i += lowbit(i); // 跳到父亲 } }图示：add(3, x)tree[3] += x → i = 3 + lowbit(3) = 4 tree[4] += x → i = 4 + lowbit(4) = 8 tree[8] += x → i = 8 + lowbit(8) = 16 > n，停止 [8] ← +x ┌─────────┘ [4] ← +x ┌─────┘ (3) ← +x ← 起点sum 函数：向下累加从位置 i 开始，一路减去 lowbit，累加经过的节点。i → i - lowbit(i) → i - lowbit(i) - lowbit(...) → ... → 0// 查询 [1, i] 的前缀和 int sum(int i) { int res = 0; while (i > 0) { res += tree[i]; i -= lowbit(i); // 跳到前一段 } return res; }图示：sum(7) tree[7] 管 [7,7] → i = 7 - lowbit(7) = 6 + tree[6] 管 [5,6] → i = 6 - lowbit(6) = 4 + tree[4] 管 [1,4] → i = 4 - lowbit(4) = 0，停止[1,4] [5,6] [7,7] tree[4] tree[6] tree[7] ← 加 ← 加 ← 起点恰好不重不漏地覆盖了 $[1, 7]$。用 add 构建树状数组建树不需要特殊技巧，对每个元素调 add 就行。vector<int> tree(n + 1); void build(vector<int>& a) { for (int i = 0; i < a.size(); i++) add(i + 1, a[i]); // 树状数组下标从 1 开始 }复杂度：$O(n \log n)$，每个元素调一次 add。优化：$O(n)$ 建树void buildLinear(vector<int>& a) { for (int i = 1; i <= n; i++) { tree[i] += a[i - 1]; // 先加上自己 int p = i + lowbit(i); if (p <= n) tree[p] += tree[i]; // 直接贡献给父亲 } }本质上就是前缀和分块：每个节点直接把它管的那段和贡献到父亲，一轮扫完。完整代码class BIT { vector<int> tree; int n; int lowbit(int x) { return x & -x; } public: BIT(int size) : n(size), tree(size + 1) {} // 用 add 构建 void build(vector<int>& a) { for (int i = 0; i < a.size(); i++) add(i + 1, a[i]); } // 位置 i 加上 x void add(int i, int x) { while (i <= n) { tree[i] += x; i += lowbit(i); } } // 查询 [1, i] 前缀和 int sum(int i) { int res = 0; while (i > 0) { res += tree[i]; i -= lowbit(i); } return res; } // 查询 [l, r] 区间和 int rangeSum(int l, int r) { return sum(r) - sum(l - 1); } };手推一遍以 a = [3, 1, 4, 1, 5, 9] 为例：建树过程：add(1, 3): tree[1]+=3, tree[2]+=3, tree[4]+=3, tree[8]+=3 add(2, 1): tree[2]+=1, tree[4]+=1, tree[8]+=1 add(3, 4): tree[3]+=4, tree[4]+=4, tree[8]+=4 add(4, 1): tree[4]+=1, tree[8]+=1 add(5, 5): tree[5]+=5, tree[6]+=5, tree[8]+=5 add(6, 9): tree[6]+=9, tree[8]+=9最终 tree 数组：i: 1 2 3 4 5 6 7 8 tree: 3 4 4 9 5 14 0 23 管辖: [1] [1,2] [3] [1-4] [5] [5,6] [7] [1-8]查询 sum(6)：i=6: tree[6]=14 (管辖 [5,6]) i=4: tree[4]=9 (管辖 [1,4]) i=0: 停止 sum = 14 + 9 = 23 验证: a[1]+...+a[6] = 3+1+4+1+5+9 = 23 ✓查询 rangeSum(2, 5)：sum(5) = tree[5] + tree[4] = 5 + 9 = 14 (3+1+4+1+5) sum(1) = tree[1] = 3 (3) rangeSum = 14 - 3 = 11 验证: a[2]+a[3]+a[4]+a[5] = 1+4+1+5 = 11 ✓add 和 sum 的对称性add: i → i + lowbit(i) → ... (向上传播修改) sum: i → i - lowbit(i) → ... (向下收集贡献)add 是在贡献数据，sum 是在收割数据。两者互逆，走的恰好是同一棵树的不同方向。 addsum方向向上（父亲）向下（前一段）跳法i += lowbit(i)i -= lowbit(i)步数≤ $\log n$≤ $\log n$操作用途修改查询复杂度操作复杂度add$O(\log n)$sum$O(\log n)$rangeSum$O(\log n)$建树 (add 逐个)$O(n \log n)$建树 (线性优化)$O(n)$空间$O(n)$总结lowbit 是灵魂 —— x & -x 管多宽、父亲是谁，全看它add 向上跳：i += lowbit(i)，通知所有管辖者sum 向下跳：i -= lowbit(i)，收集所有贡献者建树用 add：一行 add(i, a[i])，直观不出错线段树能做的区间修改，树状数组加差分也能做；但"单点改、前缀查"永远是树状数组最舒适的场景。
马拉车算法（Manacher's Algorithm）—— O(n) 求最长回文子串什么是回文串？回文串（Palindrome） 是指正读和反读都一样的字符串。例如："racecar" — 正反读都是 racecar"level" — 正反读都是 level"上海自来水来自海上" — 中文回文经典回文串分为两种：类型示例中心奇数长度"aba"单个字符 b偶数长度"abba"两个字符 bb 之间问题描述给定一个长度为 $n$ 的字符串 $s$，找出其中最长的回文子串。这是 LeetCode 第 5 题，也是面试中的经典问题。暴力解法为什么不够好？方法一：枚举所有子串string longestPalindromeBrutal(string s) { int n = s.size(); string ans; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { string sub = s.substr(i, j - i + 1); string rev = sub; reverse(rev.begin(), rev.end()); if (sub == rev && sub.size() > ans.size()) ans = sub; } } return ans; }子串数量：$O(n^2)$每个子串判断回文：$O(n)$总复杂度：$O(n^3)$ ❌方法二：中心扩展法string longestPalindromeCenter(string s) { int n = s.size(); int start = 0, maxLen = 0; for (int center = 0; center < n; center++) { // 奇数长度 int l = center, r = center; while (l >= 0 && r < n && s[l] == s[r]) { if (r - l + 1 > maxLen) start = l, maxLen = r - l + 1; l--, r++; } // 偶数长度 l = center, r = center + 1; while (l >= 0 && r < n && s[l] == s[r]) { if (r - l + 1 > maxLen) start = l, maxLen = r - l + 1; l--, r++; } } return s.substr(start, maxLen); }$2n-1$ 个中心，每个中心扩展 $O(n)$总复杂度：$O(n^2)$ — 比暴力好，但还不够快马拉车算法Manacher 在 1975 年提出 $O(n)$ 算法，核心思想：利用已经算好的回文信息，避免重复扩展。第一步：插入 # 统一奇偶在每两个字符之间插入 #，不加哨兵：原串: a b a 处理后: # a # b # a #插入后所有回文都变成奇数长度，不再区分奇偶：原串 "aa" (偶数) → "#a#a#" → 中心是中间的 '#' 原串 "aba" (奇数) → "#a#b#a#" → 中心是 'b'第二步：回文半径数组 PP[i] 表示以位置 i 为中心的最长回文半径（包含中心自身）。处理后: # a # b # a # 索引: 0 1 2 3 4 5 6 P[i]: 1 2 1 4 1 2 1P[3] = 4，以 b 为中心，半径 4，即 #a#b#a#P[1] = 2，以 a 为中心，半径 2，即 #a#原串回文长度 = P[i] - 1中心P[i]处理后回文原串回文长度b (i=3)4#a#b#a#aba3# (i=5)2#a#a1第三步：利用对称性加速维护两个变量：C — 当前最右回文的中心R — 该回文的右边界（包含），即 R = C + P[C] - 1对于当前位置 i，找它关于 C 的对称点：mirror = 2 * C - i mirror C i ↓ ↓ ↓ .....|.x..........|..........x.|... |←P[mirror]→ |← 关于C对称 →|三种情况：情况一：i > R（超出右边界）没法利用已有信息，P[i] = 1，从头扩展。[───已探索───] i ↑ 超出 R，暴力扩展情况二：i <= R 且 P[mirror] < R - i + 1（镜像完全在内部）直接复用：P[i] = P[mirror]，while 一步都不跑。[————————————C 的回文————————————R] [mirror] [i] ←P[m]→ ←P[i]→ 一样长情况三：i <= R 且 P[mirror] >= R - i + 1（镜像触及边界）知道至少 R - i + 1，从 R 往后继续扩展。——————[—————————————C的回文—————————————R] [..mirror..] [...i...] ← 太长 → ←至少R-i+1→ 继续扩代码统一写成：if (i > R) P[i] = 1; // 情况一 else P[i] = min(R - i + 1, P[mirror]); // 情况二/三取最小 while (条件) // 统一扩展，情况二第一次就失败跳过 P[i]++;可视化推演以 s = "ababa" 为例：处理后: # a # b # a # b # a # 索引: 0 1 2 3 4 5 6 7 8 9 10t = # a # b # a # b # a # 0 1 2 3 4 5 6 7 8 9 10 i=0: i>R(-1) → 情况一, P[0]=1, 越界停止 C=0, R=0 i=1: i>R(0) → 情况一, P[1]=1 扩展 t[0]=t[2]='#' → P[1]=2, 越界停止 C=1, R=2 回文区间 [0,2] = "#a#" i=2: i≤R(2), mirror=0, R-i+1=1, P[0]=1 P[2]=min(1,1)=1 → t[1]≠t[3], 停止 P[2]=1 i=3: i>R(2) → 情况一, P[3]=1 扩展 t[2]=t[4]='#', t[1]=t[5]='a', t[0]=t[6]='#' → P[3]=4 C=3, R=6 回文区间 [0,6] = "#a#b#a#" i=4: i≤R(6), mirror=2, R-i+1=3, P[2]=1 P[4]=min(3,1)=1 (情况二，直接复用) 扩展第一步即失败, P[4]=1 i=5: i≤R(6), mirror=1, R-i+1=2, P[1]=2 P[5]=min(2,2)=2 (情况三) 继续扩展: t[3]=t[7]='b', t[2]=t[8]='#', t[1]=t[9]='a', t[0]=t[10]='#' → P[5]=6 C=5, R=10 回文区间 [0,10] = "#a#b#a#b#a#" ...依此类推最终：P = [1, 2, 1, 4, 1, 6, 1, 4, 1, 2, 1]max_element(P) = 6，6 - 1 = 5 → 最长回文 "ababa" ✓完整代码int manacher(string s) { if (s.empty()) return 0; // 1. 预处理：只插入 # string t; for (char ch : s) { t += '#'; t += ch; } t += '#'; // s = "aba" → t = "#a#b#a#" int n = t.size(); vector<int> P(n); int C = 0; // 最右回文的中心 int R = -1; // 最右回文的右边界（-1 让 i=0 也走情况一） // 2. 计算回文半径 for (int i = 0; i < n; i++) { int mirror = 2 * C - i; if (i > R) P[i] = 1; // 情况一 else P[i] = min(R - i + 1, P[mirror]); // 情况二/三 // 中心扩展 while (i - P[i] >= 0 && i + P[i] < n && t[i - P[i]] == t[i + P[i]]) P[i]++; // 更新最右边界 if (i + P[i] - 1 > R) { C = i; R = i + P[i] - 1; } } // 3. max_element 找最大值，-1 即为答案 return *max_element(P.begin(), P.end()) - 1; }复杂度项目复杂度原因时间$O(n)$R 只增不减，while 总共执行 $O(n)$ 次空间$O(n)$数组 t 和 P总结三步走：插入 # → 统一奇偶，所有回文变奇数min(R - i + 1, P[mirror]) → 能抄就抄，抄不到的继续扩max_element(P) - 1 → 拿到答案