题目描述
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。
分析
关于线段树的详细讲解可以参考拙作（点击传送门）：
那么我们就开始讲解一下这一道模板题，题目的主要意思就是区间查询最小值。 首先定义线段树的节点的状态segment_tree_node struct segment_tree_node{//线段树节点状态 int Min;//表示当前区间的最小值}tree[maxn]; 接下来就是建树build的过程了。
void build(int l,int r,int nod) {//建树 if (l==r) {//如果l与r指针相撞，那么就是已经到了目标区间，赋值 tree[nod].Min=a[l]; return; } int mid=(l+r)>>1;//取中间mid build(l,mid,lson); build(mid+1,r,rson);//lson和rson可以恒定义一下，缩短代码 pushup(nod);//更新父节点} 建树好之后，我们要进行一下区间查询的操作，区间查询的本质其实就是将原区间分成两部分，然后对每一个区间的目标区间进行查询。
|----l----|----r----|当做是原区间 - 情况一：[ll,rr]区间在l区间内，那么就是
query(l,mid,ll,rr,lson)意思就是在[l,mid]区间内查询[ll,rr] - 情况二：[ll,rr]区间在r区间内，那么就是
query(mid+1,r,ll,rr,lson)意思就是在[mid+1,r]区间内查询[ll,rr] 情况三：[ll,rr]区间一部分在l区间内，一部分在r区间内，那么就要把原区间和目标区间都分成两部分，因为线段树中同一深度的区间互不干扰，那么我们就查询
query(l,mid,ll,mid,lson),query(mid+1,r,mid+1,rr,rson)注：区间查询一般是不需要pushup的，但是如果之前是有区间修改，那么是要pushdown的。
那么我们通过代码来详细的看一下区间查询最小值是如何写的。
int query(int l,int r,int ll,int rr,int nod) {//区间查询最小值 if (l==ll&&r==rr) return tree[nod].Min;//已经找到了目标区间 int mid=(l+r)>>1;//取中间 if (rr<=mid) return query(l,mid,ll,rr,lson);//整个区间在mid的左边 else if (ll>mid) return query(mid+1,r,ll,rr,rson);//整个区间在mid的右边 else return min(query(l,mid,ll,mid,lson),query(mid+1,r,mid+1,rr,rson));//区间被mid分成两部分} 主程序就不写了，也是很简单的
恒定义：define lson nod<<1 define rson (nod<<1)+1
完整代码
#include#define lson nod<<1#define rson (nod<<1)+1#define ms(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn=100000<<2;const int inf=1<<30;struct segment_tree_node{//线段树节点状态 int Min;}tree[maxn];int n,m;int a[maxn>>2];inline int read() { int x=0,w=0; char ch=0; while (!isdigit(ch)) {w|=ch=='-';ch=getchar();} while (isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return w?-x:x;}void pushup(int nod) {//pushup操作，更新父节点内的信息 tree[nod].Min=min(tree[lson].Min,tree[rson].Min);}void build(int l,int r,int nod) {//建树 if (l==r) {//如果l与r指针相撞，那么就是已经到了目标区间，赋值 tree[nod].Min=a[l]; return; } int mid=(l+r)>>1;//取中间mid build(l,mid,lson); build(mid+1,r,rson);//lson和rson可以恒定义一下，缩短代码 pushup(nod);//更新父节点}int query(int l,int r,int ll,int rr,int nod) {//区间查询最小值 if (l==ll&&r==rr) return tree[nod].Min;//已经找到了目标区间 int mid=(l+r)>>1;//取中间 if (rr<=mid) return query(l,mid,ll,rr,lson);//整个区间在mid的左边 else if (ll>mid) return query(mid+1,r,ll,rr,rson);//整个区间在mid的右边 else return min(query(l,mid,ll,mid,lson),query(mid+1,r,mid+1,rr,rson));//区间被mid分成两部分}int main() { ms(tree,inf);//先将树的每一个节点都赋值成inf，因为我们要求最小值 n=read(),m=read(); for (int i=1;i<=n;i++) a[i]=read(); build(1,n,1); while (m--) { int x=read(),y=read(); printf("%d ",query(1,n,x,y,1)); } return 0;}