46| FBI树

一、核心思路

用前缀和快速判断区间类型，递归不断二分，先分左右，最后输出自己，就是 FBI 树。

1.前缀和预处理（快速查区间）

• f[i]存：前 i 个字符里1 的个数
• 想知道[l, r]是什么类型：
  • 和为 0 → B
  • 和 = 长度 → I
  • 其他 → F

2. 递归分治（核心）

把当前字符串分成左右两半：

• 左：l ~ mid
• 右：mid+1 ~ r

一直分，分到不能再分（只剩一个字符）为止。

3. 叶子节点直接输出

分到最小单位

• 输出 B/I
• 立刻返回，不再继续分割
• 防止无限递归、越界

二、代码实现

#include <bits/stdc++.h> using namespace std; #define int long long const int N = 11; int f[1 << N]; int n; void dfs(int l, int r) { if(l > r) return; char ret; // 判断字串类型 if (f[r] - f[l-1] == (r - l + 1)) ret = 'I'; else if (f[r] - f[l-1] == 0) ret = 'B'; else ret = 'F'; // 递归构建 if(l == r) // 叶子节点直接输出 { cout << ret; return; } int mid = (l + r) >> 1; dfs(l, mid); // 左子树 dfs(mid + 1, r); // 右子树 cout << ret; // 根节点 } signed main() { cin >> n; n = (1 << n); for (int i = 1; i <= n; i++) { int t = 0; char ch; cin >> ch; if(ch == '1') t = 1; f[i] = f[i-1] + t; } dfs(1,n); return 0; }