看了一天的线段树了，真心觉得这算法好难，虽然是模板，但每个题目不是给个模板就能AC的吧，看是得慢慢把算法弄懂，我觉得不会码倒在其次，要能在看到题目变动的时候适时改变算法。
//线段树模板
struct line
{
int left,right;//左端点、右端点
int n;//记录这条线段出现了多少次，默认为0
};
struct line a[100];
int sum;
//建立
void build(int s,int t,int n)
{
int mid=(s+t)/2;
a[n].left=s;a[n].right=t;
if (s==t) return;
a[n].left=s;a[n].right=t;
build(s,mid,2*n);
build(mid+1,t,2*n+1);
}
//插入
void insert(int s,int t,int step)//要插入的线段的左端点和右端点、以及当前线段树中的某条线段
{
if (s==a[step].left && t==a[step].right)
{
a[step].n++;//插入的线段匹配则此条线段的记录+1
return;//插入结束返回
}
if (a[step].left==a[step].right)
return;//当前线段树的线段没有儿子，插入结束返回
int mid=(a[step].left+a[step].right)/2;
if (mid>=t)
insert(s,t,step*2);//如果中点在t的右边，则应该插入到左儿子
else if (mid<s)
insert(s,t,step*2+1);//如果中点在s的左边，则应该插入到右儿子
else//否则，中点一定在s和t之间，把待插线段分成两半分别插到左右儿子里面
{
insert(s,mid,step*2);
insert(mid+1,t,step*2+1);
}
}
//访问
void count (int s,int t,int step)
{
if (a[step].n!=0) sum=sum+a[step].n*(t-s+1);
if (a[step].left==a[step].right) return;
int mid=(a[step].left+a[step].right)/2;
if (mid>=t) count(s,t,step*2);
else if (mid<s) count(s,t,step*2+1);
else
{
count(s,mid,step*2);
count(mid+1,t,step*2+1);
}
}
线段树的定义
定义1 长度为1的线段称为元线段。
定义2 一棵树被成为线段树，当且仅当这棵树满足如下条件：
（1） 该树是一棵二叉树。
（2） 树中每一个结点都对应一条线段[a,b]。
（3） 树中结点是叶子结点当且仅当它所代表的线段是元线段。
（4） 树中非叶子结点都有左右两个子树，做子树树根对应线段[a , (a + b ) / 2]，右子树树根对应线段[( a + b ) / 2 , b]。
但是这种二叉树较为平衡，和静态二叉树一样，提前根据应用的部分建立好树形结构。针对性强，所以效率要高。一般来说，动态结构较为灵活，但是速度较慢；静态结构节省内存，速度较快。
线段树的性质与时空复杂度简介
下面介绍线段树的两个性质（证明略）。
性质1 长度范围为[1,L]的一棵线段树的深度不超过log(L-1) + 1。
性质2 线段树把区间上的任意一条长度为L的线段都分成不超过2logL条线段。
空间复杂度 存储一棵线段树的空间复杂度一般为O（L）。
时间复杂度 对于插入线段、删除线段，查找元素，查找区间最值等操作，复杂度一般都是O（log L）。
线段树主要应用了平衡与分治的性质，所以基本时间复杂度都和log有关。我们在应用线段树解决问题的时候，应尽量在构造好线段树的时候，使每种操作在同一层面上操作的次数为O（1），这样能够维持整体的复杂度O（log L）。
例题：RMQ with Shifts
Description
Input
There will be only one test case, beginning with two integers n, q (1<=n<=100,000, 1<=q<=120,000), the number of integers in array A, and the number of operations. The next line contains n positive integers not greater than 100,000, the initial elements in array A. Each of the next q lines contains an operation. Each operation is formatted as a string having no more than 30 characters, with no space characters inside. All operations are guaranteed to be valid. Warning: The dataset is large, better to use faster I/O methods.
Output
For each query, print the minimum value (rather than index) in the requested range.
Sample Input
Sample Output
HINT
分析：根据模板，添加了两个函数query()-用来查询-和update()-用来更新数据。
代码：
#include<iostream>
#include<cstdio>
#include<stdio.h>
#include<cstring>
using namespace std;
struct line{
int left,right,n;
int mid(){return (left+right)/2;}
}a[100011<<2];
unsigned short num[100011];
int temp[33],cnt;
void build(int l,int r,int step)
{
a[step].left=l;
a[step].right=r;
if(l==r)
{
a[step].n=num[l];
return;
}
int mid=a[step].mid();
build(l,mid,step*2);
build(mid+1,r,step*2+1);
a[step].n=min(a[step*2].n,a[step*2+1].n);
}
int query(int l,int r,int step)
{
if(a[step].left==l&&a[step].right==r)
return a[step].n;
int mid=a[step].mid();
if(mid>=r)
return query(l,r,step*2);
else if(mid<l)
return query(l,r,step*2+1);
else
return min(query(l,mid,step*2),query(mid+1,r,step*2+1));
}
void update(int l,int r,int step)
{
if(a[step].left==a[step].right)
a[step].n=num[a[step].left];
else
{
int mid=a[step].mid();
if(mid>=temp[r])
update(1,r,step*2);
else if(mid<temp[l])
update(1,r,step*2+1);
else
{
int i;
for(i=1;temp[i]<=mid;i++) ;
update(1,i-1,step*2);
update(i,r,step*2+1);
}
a[step].n=min(a[step*2].n,a[step*2+1].n);
}
}
bool judge(char *p)//注意字符的处理
{
char t=p[0];
p=p+6;
while(strlen(p))
{
int bit;
sscanf(p,"%d%n",&temp[cnt++],&bit);
p=p+bit+1;
}
if(t=='q') return true;
return false;
}
int main()
{
int n,m,i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
build(1,n,1);
char str[33];
while(m--)
{
scanf("%s",&str);
cnt=1;
if(judge(str))
printf("%d
",query(temp[1],temp[2],1));
else
{
cnt--;
int flag=num[temp[1]];
for(i=1;i<cnt;i++)
num[temp[i]]=num[temp[i+1]];
num[temp[i]]=flag;
update(1,cnt,1);
}
}
}
}