kevin日志 - 2026年8月
type: channel
link: https://www.bananaandpotato.top/index.php/2026/08/
description: kevin
items: 树状数组
items: 马拉车算法 —— 求最长回文子串

树状数组
type: item
date: 2026-08-01T16:09:00+08:00
description: 树状数组（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]; // 直接贡献给父亲 } }本质上就是前缀和分块：每个节点直接把它管的那段和贡献到父亲，…

马拉车算法 —— 求最长回文子串
type: item
date: 2026-08-01T15:52:00+08:00
description: 马拉车算法（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（镜…