【题解】完全二叉树的权值

题目链接：完全二叉树的权值

双指针

1. 用两个指针分别指向每一层的起点和终点，枚举每一层之和，找到总和最大的最小层数。

前缀和

1. 设给定二叉树共 depth 层，前 d - 1 层（第 d 层可以为 0 ，也可以为满）满足：2⁰ + 2¹ + 2² + … + 2^d-1 = (2^d) - 1 ，也即 2^d -1 <= n，可得 d <= log₂ⁿ⁺¹ ，将底数换成 e 可得 d <= (log_eⁿ⁺¹) / (log_e²) ， 由于这是通过前 d - 1 层得到的，所以层数depth = d + 1 。
2. 换句话说就是计算所得层数要向上取整，因为最后一层可能不满，此时计算 $\log_2 n+1$ 会比实际层数少一层，所以要加 1 。
3. 第 d 层的区间是 [1 << (d - 1), min((1 << d) - 1, n)] 。

本题细节

1. log 函数默认以 e 为底。
2. 本题需要 long long 。 int 最多存大小在正负 20 亿之间的数据，也即 -2e9 ~ 2e9 之间。

法一：双指针

c++ 71ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second


const int N = 1e5 + 10;

int n;
int a[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    pair<LL, LL> p = {0, -0x3f3f3f3f};
    for (int i = 1, u = 1; i <= n; i *= 2, u ++ )
    {
        LL sum = 0;
        for (int j = i; j <= i * 2 - 1 && j <= n; j ++ )
            sum += (LL)a[j];
        if (sum > p.second) 
        {
            p.second = sum;
            p.first = u;
        }
    }

    cout << p.first << endl;
    return 0;
}

法二：前缀和

c++ 77ms

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <map>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
#define x first
#define y second


const int N = 1e5 + 10;

int n;
LL s[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) 
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    PII p = {0, -1e18};
    int depth = log(n + 1) / log(2) + 1;
    for (int d = 1; d <= depth; d ++ )
    {
        // 第 d 层的区间是 [1 << (d - 1), min((1 << d) - 1, n)]
        int u = (1 << d) - 1;
        int l = 1 << (d - 1), r = min(u, n);

        LL sum = s[r] - s[l - 1];
        if (sum > p.second)
        {
            p.second = sum;
            p.first = d;
        }
    }

    cout << p.first;
    return 0;
}