前缀和做法

用前缀和解决。但是被一组数据卡了好久
就是当n=1e5的时候，因为1e5个结点构成的不是满二叉树（第十七层的结点没有填满），所以只能特殊处理一下！
一开始想成了满二叉树，难受

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
const int N=1e5+5;
using namespace std;
int a[N];
long long s[N];//前缀和 
long long st[25];//每一层的和 
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)s[i]=a[i]+s[i-1];
    bool tag=false;
    for(int i=1;pow(2,i)-1<=n;i++){//i是层数
        long long l=pow(2,i-1),r=pow(2,i)-1;
        //在i=17时 r=131072 超过开的数组范围，
        //从出错的测试数据100000看，最后这一层并没有填满
        st[i]=s[r]-s[l-1]; 
    }
    int t=pow(2,16)-1;
    if(n>65535)st[17]=s[n]-s[t];//下
    //65535是第16层的最后一个结点
    int max=1;
    for(int i=1;i<=17;i++){
        if(st[i]>st[max])max=i;
    }
    cout<<max<<"\n";
    return 0;
}

双指针做法

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N=1e5+10;
int n,a[N]; 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    //d是层数，i是每一层第一个的位置 
    int depth=0;
    long long max=-1e18;
    for(int d=1,i=1;i<=n;i*=2,d++){
        long long s=0;
        for(int j=i;j<i+(1<<d-1)&&j<=n;j++){
            //1<<d-1就是pow(2,d-1),先算加减再位运算 
            //因为最后一层肯能不满，还需要j<=n 
            s+=a[j];
        }
        if(s>max){
            max=s;
            depth=d;
        }
    }
    cout<<depth<<"\n";
    return 0;
}