完全二叉树的每层权值

原题链接

给定一个下标从1开始的一维数组，代表一颗完全二叉树。问题就是求二叉树中每层结点的权值之和。

本题的关键即：如何快速枚举完全二叉树的每一层？

令根结点位于第1层，则第 d d d层的首元素在数组中的下标为： 2 d − 1 2^{d-1} 2d−1，第 d d d层的元素个数为： 2 d − 1 2^{d-1} 2d−1。

#include 
using namespace std;
typedef long long LL;

const int N = 100010;
int a[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    LL maxs = -1e18;
    int depth = 0;

    for (int i = 1, d = 1; i <= n; i *= 2, d ++) //i枚举每层的首元素，d枚举层数  
    {
        LL s = 0;
        for (int j = i; j < i + (1 << d - 1) && j <= n; j ++) s += a[j]; // [  i,  min(i + 2^{d-1} - 1, n)  ]

        if (s > maxs)
        {
            maxs = s;
            depth = d;
        }
    }

    cout << depth;
    return 0;
}