【题目描述】
AcWing 1240. 完全二叉树的权值

【思路】
二叉树性质 前缀和
只要知道每一层节点的起始索引和结束索引就可以根据前缀和计算这一区间的和。
每一层开始索引p,结束索引q,节点为f[p：q]，关键就是求出p、q。易得p为山一层结束索引加1，q为包括当前层所有节点个数。

而满二叉树每一层的节点数：1 2 4 8 16 32 64……
当前层的节点数为上一层节点数的两倍。

求出树的高度（深度） h：
     int h = 1;
        int res = 1, last = 1;
        while( res < n){//
            last *= 2; //当前层的节点数为上一层节点数的两倍。 
            res += last;
            h ++;
        }

for(深度)：
    求出每一层的起始索引p和结束索引q
    统计该层的权值和long tmp = sum[q] - sum[p - 1];
    if(tmp > ans) {
                ans =tmp;
                answer = i;
            }

据此可以在O(n)时间求得问题的解。

import java.io.*;
import java.lang.Math;
public class Main{
    static int N = 100010;
    static int f[] = new int[N];
    static long sum[] = new long[N];
    public static void main(String args[]) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        String s[] = bf.readLine().split(" ");
        for(int i = 1; i <= n; i ++)
            f[i] = Integer.parseInt(s[i - 1]);
        //前缀和
        for(int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + f[i];


        int h = 1;
        int res = 1, last = 1;
        while( res < n){//
            last *= 2; //当前层节点的个数为上一层节点数的2倍
            res += last;
            h ++;
        }
        int answer = 1; //记录深度
        long ans = f[1];    //当前最大值
        int k = 1, cnt = 1; //k表示当前层的节点数
        int p = 1, q = 1;
        //计算每一层的权值
        for(int i = 2; i <= h; i++){

            k *= 2; //当前层节点数是上一层的2倍
            cnt += k;// cnt记录[1 ~i]层的总节点数
            //当前层的节点为：f[p:q]
            p = q + 1;
            q = (cnt > n ? n: cnt);
            long tmp = sum[q] - sum[p - 1];
            if(tmp > ans) {
                ans =tmp;
                answer = i;
            }

        }
        System.out.println(answer);



    }
}

【思路】
快速幂 满二叉树性质 前缀和

根据等比数列前n项和公式，可以得出满二叉树总节点数(n)与总层数(h)的关系： 2^ h = n + 1 。但是要注意这里是是完全二叉树不是满二叉树，所以 2^h>= h + 1

若是满二叉树，则从第一层到当前层i，节点数为 2^h - 1。但是这里是完全二叉树，所以最后一层要特判一下。

import java.io.*;
import java.lang.Math;
public class Main{
    static int N = 100010;
    static int f[] = new int[N];
    static long sum[] = new long[N];

    //快速求解 x^n
    static int quick_pow(int x, int n){
        int pingfang = 1, res = x;
        while(n > 0){
            if( (n&1) == 1){
                pingfang *= res;
            }
            n/=2;
            res *= res;
        }
        return pingfang;
    }
    public static void main(String args[]) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        String s[] = bf.readLine().split(" ");
        for(int i = 1; i <= n; i ++)
            f[i] = Integer.parseInt(s[i - 1]);
        //前缀和 
        for(int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + f[i];

        //根据等比数列前n项和公式，得出满二叉树总节点数(n)与总层数(h)的关系： 2^ h = n + 1 
        int h = 1;
        for(; h <= n; h ++)
            if( quick_pow(2, h) >= n + 1) break;

        //System.out.println(h);
        int ans = 1;
        long res = f[1];
        int p = 1, q = 1;
        for(int i = 2; i <= h; i ++){

            p = q + 1;
            int cnt = quick_pow(2,i) - 1; //当前层最后一个节点为 2^h - 1
            q = (cnt > n? n: cnt);
            long tmp = sum[q] - sum[p - 1];
            if(tmp > res){
                res =tmp;
                ans = i;
            }
        }
        System.out.println(ans);



    }
}