上次学的ST算法解决线段树写法，然后发现线段树其实也可以解决这个问题，不知道为什么我对树有一点阴影，一开始我一直不敢学呜呜呜，还是得慢慢一点点前进！
例题： balanced upline 有n头母牛 接下来一行有n个数表示每头母牛的高度，他们的位置是1-n。 给出T组查询区间，找出区间中（含端点）最小的母牛高度。
如果仅仅是这样，用ST写法可以很快的求出，属于直接套模板的题，稍微给自己加点难度，（正好试着学一下线段树），放一个修改操作。
稍改后的题： 有n头母牛 接下来一行有n个数表示每头母牛的高度，他们的位置是1-n。 现有两个操作分别用0，1表示。 操作0：给出两个数l，r，求出区间【l，r】间最小的母牛高度并输出； 操作1：给出两个数pos，val，将第pos只母牛高度修改成val。 有T行操作，每行操作含三个数，第一个数表示操作。
n<=1e6,1<=l<=r<=n,1<=pos<=n,val<=1e6;
样例输入 5 40 10 20 30 2 6 0 4 5 0 2 4 1 4 6 0 3 4 1 3 4 1 3 20 样例输出 2 10 6
啥也不说，先给代码：
/*the trees will never defeat me forever, for all the trees is the scenery on the ACM roads ————luxun */ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<string> #include<vector> #include<stack> #include<bitset> #include<cstdlib> #include<cmath> #include<set> #include<list> #include<deque> #include<map> #include<queue> #define LL long long #define pb push_back using namespace std; const int maxn=1e5+7; struct node { int l,r,minn; } tree[maxn]; int arr[maxn]; int n,m,i,j,f,mini,k,T; //建树 void build(int id,int l,int r) { tree[id].l=l; tree[id].r=r; if (l==r) tree[id].minn=arr[l];//如果区间左右端点重合，则不需要继续分区间 else { int mid=(l+r)/2; build(id*2,l,mid);//递归建左子树 build(id*2+1,mid+1,r);//递归建右子树 tree[id].minn=min(tree[id*2].minn,tree[id*2+1].minn);//父节点的最小值即两个分区间的最小值中较小的值 } } void update(int id,int pos,int val) { if (tree[id].l==pos&&tree[id].r==pos) { tree[id].minn=val; return; } if (pos>(tree[id].l+tree[id].r)/2) //右子树 { update(id*2+1,pos,val); } else //左子树 { update(id*2,pos,val); } tree[id].minn=min(tree[id*2].minn,tree[id*2+1].minn); } void search(int id,int l,int r) { if (l<=tree[id].l&&r>=tree[id].r)//不断更新最小值mini { mini=min(mini,tree[id].minn); } else { int k=(tree[id].l+tree[id].r)/2; if (l>k) { search(2*id+1,l,r); } else { if (r<=k) { search(2*id,l,r); } else { search(2*id,l,r); search(2*id+1,l,r); } } } } int main() { cin>>n; for (i=1; i<=n; i++) { cin>>arr[i]; } build(1,1,n); cin>>T; while(T--) { cin>>f; mini=0x7fffffff; if (f) { int q,w; cin>>q>>w; update(1,q,w); } else { int l,r; cin>>l>>r; search(1,l,r); cout<<mini<<endl; } } return 0; }给出自己初学线段树对线段树的理解：
之前的基础树结点基本上只表示一个数，也就是给我们一个一维数组，我们根据维护大小关系或者别的方式维护，最典型的例子是最大堆和最小堆。线段树顾名思义就是维护线段，那么怎么维护呢？
建树： 每一个结点其实是一个结构体，这个结构体里面含有三个数，分别是区间左端点，右端点和这个区间的最小值，也就相当于把区间的最小值都存起来了。如果根结点是【1，n】，我们要求【1，n】中的最小值，就可以求数组前半段【1，mid】和数组后半段【mid+1，n】的最小值，然后取其中较小者作为【1，n】的最小值。如此把每一段区间慢慢分下去，就可以建成一个完整的线段树了。那么比较简单的实现方式就是树论中常见的递归了。
更新树和查找树： 更新树的关键就是找出要修改的树的位置，那么肯定就是找到l=r=pos的地方，用递归查找很容易实现。
查找树的关键就是不断递归，只要【tree[id].l,tree[id].r】区间含在所求区间【l，r】中时，就可以更新【l，r】的最小值，一时更新一时爽，所以一直更新就能更新出最终答案了！ 不要忘了这句话 ，很容易遗忘！ 总体来说，基础线段树的理解不难，我相信后期线段树的衍生不会让我失望的（微笑面对生活
