本篇只讲简单的线段树，仅建树、求区间最大/最小值。
其他大佬的模版都比较长，不易理解，读起来也比较费劲，今天分享一款比较简短的蒟蒻式模版
废话不多说，有点二叉树基础的狗友都知道：
（仅节点编码）
那么我们的模版也会根据这个小知识点进行扩张
1.建树
#include<bits/stdc++.h>
using namespace std;
int tree[405];
int a[105];
void build(int root,int l,int r)
{
if (l<r) return tree[root]=a[l];
int mid=(l+r)/2;
return tree[root]=min(build(root2,l,mid),build(root2+1,mid+1,r));//最小值
//return tree[root]=max(build(root2,l,mid),build(root2+1,mid+1,r));//最大值
}
int main()
{
int n;
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
build(1,1,n);
return 0;
}
这就是建树，其中思路与归并排序类似，递归从根节点开始分别向其左子树与其右子树遍历建树
tree[i]表示节点编号为i的线段树节点的存值
橙色为原数组区间，红色为节点存值，黑色为节点编号。
本图以最大值建树为例
即节点存的值是其左子树与右子树中的最大值
举个栗子：节点1存的就是区间[1,2]与区间[3,4]合并所得的最大值
模拟过程
1.递归区间[1,4]
条件不成立，递归结果max([1,2],[3,4])
2.递归区间[1,2]
条件不成立，递归结果max([1,1],[2,2])
3.两个子区间条件成立，回溯至2
4.结果为[2,2]，回溯至1
5.递归区间[3,4]
条件不成立，递归结果max([3,3],[4,4])
6.两个子区间条件成立，回溯至5
7.结果为[4,4]，回溯至1
8.结果为[1,2]，递归结束，建树成功
好了，咱们已经获得了一棵优美的维护最大值的线段树了，接下来就是查询了
2.查询
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005];
int tree[4000005];//顺序存储法
int built(int root,int l,int r)//返回[l,r]的最大值
{
if (l==r) return tree[root]=a[l];//维护叶节点
int mid=(l+r)/2;
return tree[root]=max(built(root2,l,mid),built(root2+1,mid+1,r));
}
int query(int root,int l,int r,int ql,int qr)//返回[ql,qr]的最大值
{
if (qr<l||r<ql) return INT_MIN;//要求最大值返回最小值，反之亦然
if (ql<=l&&r<=qr) return tree[root];//叶子节点
int mid=(l+r)/2;
return max(query(root2,l,mid,ql,qr),query(root2+1,mid+1,r,ql,qr));//维护最大值
}
int main()
{
scanf("%d %d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
built(1,1,n);
while(m--)
{
int x,y;
scanf("%d %d",&x,&y);
printf("%d\n",query(1,1,n, x,y));//查询区间
}
return 0;
}
