树状数组：区间求和。

对于一个长度为n的数组，询问多次(i,j)区间的最大（最小值）。

RMQ：区间求最值问题。

1、暴力搜索，时间复杂度：O(n^2)

2、树状数组把sum改成max/min（不常用，基础操作，较为繁琐）

3、ST表（ST算法），基于动态规划，处理数据时间O(nlogn)，查询O(1)

4、线段树，基于分治

ST表

状态 st[i][j] 从i开始2^j个数字中，最大值

方程 st[i][j]=max/min(st[i][j-1],st[i+2^(j-1)][j-1]);

求[x,y]最大值

模板题：1541题，1542题，1544题

ST模板

//构建ST表

vector<vector<int>> buildST(vector<int>& nums){

   int n=nums.size();

   int k=log2(n);//对数函数 2^k<=n <cmath>

   vector<vector<int>> st(n,vector<int>(k,0));

   for(int i=0;i<n;i++) st[i][0]=nums[i];

   for(int j=1;j<=k;j++)

       for(int i=0;i+(1<<j)-1<n;i++)

           st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);

   return st;

}

int log2(int n){

int log=0;

while(n/=2) log++;//while(n >>= 1) log++;

return log;

}

int getMax(const vector<vector<int>>& st,int i,int j){

int k=log2(j-i+1);

return max(st[i][k],st[j-(1<<k)+1][k]);

}

输入一个十六进制的数字，以十进制数出

int n;

cin>>hex>>n;//只有十六进制 hex 八进制 oct

cout<<n;

模板题：1541题，1542题，1544题