看了一天的线段树了，真心觉得这算法好难，虽然是模板，但每个题目不是给个模板就能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
    
     =t) count(s,t,step*2);    else if (mid
    

 

 

线段树的定义

定义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

In the traditional RMQ (Range Minimum Query) problem, we have a static array A. Then for each query (L, R) (L<=R), we report the minimum value among A[L], A[L+1], …, A[R]. Note that the indices start from 1, i.e. the left-most element is A[1].

In this problem, the array A is no longer static: we need to support another operation shift(i1, i2, i3, …, ik) (i1<i2<...<ik, k>1): we do a left “circular shift” of A[i1], A[i2], …, A[ik].

For example, if A={6, 2, 4, 8, 5, 1, 4}, then shift(2, 4, 5, 7) yields {6, 8, 4, 5, 4, 1, 2}. After that, shift(1,2) yields {8, 6, 4, 5, 4, 1, 2}.

 

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

7 5

6 2 4 8 5 1 4

query(3,7)

shift(2,4,5,7)

query(1,4)

shift(1,2)

query(2,2)

Sample Output

146

HINT

分析：根据模板，添加了两个函数query()-用来查询-和update()-用来更新数据。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         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
         
          =temp[r])            update(1,r,step*2);        else if(mid