AcWing
1240. 完全二叉树的权值
注意区分完全二叉树和满二叉树。
假设一共有n层，先遍历1 ~ n-1层，记录最大和与层高；再单独判断最后一层。
据说可以用双指针：每层的开头为$2^{n-1}$，结尾则是$2^n - 1$，计算每层的数值只需要两个指针，分别指向开头和结尾。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010;
int a[N];
typedef long long LL;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
LL msum = a[1] - 1; // 全局的最大和
int idx = 1, lev = 1, res; // 当前数组索引、当前层数、结果
for(int cnt = 1; idx + cnt - 1 <= n; cnt <<= 1, lev ++){
LL sum = 0;
for(int i = idx; i <= idx + cnt - 1; i ++) sum += a[i];
if(sum > msum) msum = sum, res = lev;
idx = idx + cnt;
}
// 处理不足cnt的最后一层
LL sum = 0;
for(; idx <= n; idx ++) sum += a[idx];
if(sum > msum) msum = sum, res = lev;
cout << res;
}