一. 区间最大最小值问题

　　1. RMQ

int mx[N][20];                      //最多能保存524288的长度int RMQ(int l, int r)   {    int k = 0;  while (1<<(k+1) <= r - l + 1)   k++;        //令k为满足1<
     
      <= r-l+1的最大整数    return max (mx[l][k], mx[r-(1<
     

　　2. Segment_Tree

struct ST    {    int mx[N<<2];    void push_up(int rt)    {        mx[rt] = max (mx[rt<<1], mx[rt<<1|1]);    }    void build(int l, int r, int rt)    {        if (l == r)    {            scanf ("%d", &mx[rt]);    return ;        }        int mid = (l + r) >> 1;        build (lson);　　build (rson);        push_up (rt);    }    int query(int ql, int qr, int l, int r, int rt)    {        if (ql <= l && r <= qr)    {            return mx[rt];        }        int mid = (l + r) >> 1, ret = 0;        if (ql <= mid)    ret = max (ret, query (ql, qr, lson));        if (qr > mid)    ret = max (ret, query (ql, qr, rson));        return ret;    }}st;