题目链接：P4715 【深基16.例1】淘汰赛 - 洛谷 | 计算机科学教育新生态
题目难度：普及
刷题心得：本题是我二刷，之前第一次刷是在洛谷线性表那个题单，当时印象深刻第 一篇题解是用的树来做，当时我不屑一顾（觉得花里胡哨），现在我开始刷树的题目着字分析，第一次学习到线性树的用法现在把他总结下
线段树
线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。比如说一个长度为4的线段，我们可以表示成这样：
这是什么意思呢？ 如果你要表示线段的和，那么最上面的根节点的权值表示的是这个线段 1 ∼ 6 的和。根的两个儿子分别表示这个线段中 1 ∼ 3 和4 ~6的和，以此类推。
然后我们还可以的到一个性质：节点 i的权值 == 它的左儿子权值 +它的右儿子权值。
我们知道，一颗从 1 11 开始编号的二叉树，结点 i的左儿子和右儿子编号分别是i x 2 和 i x 2 + 1
建树代码：
void build(int node,int start,int end){ //建树函数，参数是根节点和左右区间 if(start==end){ //如果两边相等 tree[node]=arr[start]; //填的就是数组里的初始值 return; //递归边界 }int leftnode=node*2; //算出左右节点（完全二叉树的性质） int rightnode=node*2+1; int mid=(start+end)/2; //把数组从中间劈成两半build(leftnode,start,mid); //左边右边分开建树 build(rightnode,mid+1,end);tree[node]=tree[leftnode]+tree[rightnode]; //根节点的值=左根+右根
}查询和求区间和：
void update(int node,int start,int end,int id,int val){ //修改操作，参数分别是建树函数的那三个和修改节点的编号和修改的值if(start==end){ //递归边界，如果是叶节点tree[node]+=val; //修改node节点的值return;}int leftnode=node*2; //算出左右子树和中点int rightnode=node*2+1; int mid=(start+end)/2; if(id>=start&&id<=mid) //如果要改的地方在中点左边update(leftnode,start,mid,id,val);//那就递归修改左子树else update(rightnode,mid+1,end,id,val);//要么就递归修改右子树 tree[node]=tree[leftnode]+tree[rightnode]; //根节点更新
}
int query(int node,int start ,int end,int l,int r){ //查询函数，l和r是求和的左右区间if(l<=start&&r>=end) //如果求和的区间已经当前的部分包含了
//（比如当前在[1,3]区间，让你求[1，5]，那你就要求[1,3]+[4,5]，直接把建树的时候算好的[1,3]的和加上去就行了）return tree[node]; //直接返回根节点int leftnode=node*2; //又双叒叕是左右子树和中点int rightnode=node*2+1; int mid=(start+end)/2;int sum=0; //就是要返回的和啊 if(l<=mid) //如果要求和的区间包含中点左边的部分sum+=query(leftnode,start,mid,l,r); //那就加上左边那块if(r>mid) //同理，如果右边还有那就加上右边那块sum+=query(rightnode,mid+1,end,l,r);return sum; //返回sum，不解释
}线段树好处：所以介绍了这么多线段树，线段树到底有什么用前缀和不是也可以求和吗，可是如果修改一个值再求和前缀和，每一个前缀和都要修改时间复杂度就是o(n)了，线段树它可以把时间复杂度降低降低再降低，把修改和查询的时间复杂度都降到O(logn)。
最后奉上本题代码：
#include<bits/stdc++.h> // 万能头文件
using namespace std;
typedef long long ll;
//const int N = 100010;
int n;struct node{int power;//能力值 int id;//国家序号
}a[150],tree[600]; //a用来存储数据，tree是存线段树的数组 node maxn(node a,node b){ //返回两个结构体里能力值更大的那个return a.power>b.power?a:b;
}
node minn(node a,node b)
{return a.power < b.power ? a : b;//返回两个结构体里能力值更小的那个
}
void build(int node,int start,int end)//建树函数，参数是根节点和左右节点
{if(start == end)//两边相等 {tree[node] = a[start];//填的就是数组的初始值 ,即叶子节点不需要划分 return;//边界 }int leftNode = node * 2;//算出左右节点（完全二叉树的性质） int rightNode = node * 2 + 1;int mid = (start + end) / 2;//把数组从中间分开 build(leftNode,start,mid);build(rightNode,mid + 1,end);tree[node]= maxn(tree[leftNode],tree[rightNode]); //父节点是左右子节点里更大的;
}
int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;for(int i=1; i<= (1<<n); i++){cin >> a[i].power;a[i].id = i;}build(1,1,(1<<n));cout<<minn(tree[2],tree[3]).id;return 0;
}
