st（树状数组版）
哲学家
·
·
个人记录
定理1、众所周知，线段树是拿来练习树状数组的（雾）。
定理2、用线段树能切ST表
结论：树状数组能切线段树 + 线段树切了ST表 = 树状数组能切ST表 √（逻辑鬼才）
所以我们来康康树状数组怎么维护区间最大值：
1、求lowbitlowbit
由于是树状数组，当然需要求lowbitlowbit
这点就不过多赘述了。如果不懂就去点最上面的链接awa。
int lowbit(int x)
{
return x & -x;
}
2、建树，维护最大值
如何用树状数组维护最大值？
首先呢，我们知道树状数组如何维护区间和。本质是一个不断向上递归传递的过程。每次递归就把当前点的值给加上去。
维护区间和是加，维护最大值自然就是求最大值了。
void _add(int x, int k)//建树QAQ x表示树状数组点的编号，k表示需要传递的值
{
for(;x <= n; x += lowbit(x))
tree[x] = max(tree[x], k); //把 + 改为了max()
}
这个应该浅显易懂吧...
值得一提的是，这个函数还可以用来进行单点修改操作。 就像求区间和那样...但是这题不用啊QAQ。感觉有点大材小用了...
3、查询区间最大值（划重点）
上面有提到过，建树时可以直接套区间和的板子，只需要把累加改成求最值就可以了。
但是查询不行啊啊啊...这是为什么呢？
回想一下我们如何用树状数组求区间和？ 假设我们要求出[x, y][x,y]的区间和，我们可以先求出[1,x-1][1,x−1]的区间和与[1,y][1,y]的区间和，再把他们相减。这样就求到了[x, y][x,y]的区间和啦。
但是最大值显然不行。当然你可以试试用[1,y][1,y]区间的最大值减[1,x-1][1,x−1]区间的最大值，看能不能输出正确答案。
好吧，那我们怎么处理查询问题？？
我们分两种情况讨论：
1、 y-lowbit(y) > xy−lowbit(y)>x
这种情况下，我们可以把求[x,y][x,y]区间的最大值拆分成两部分，先求[x,y-lowbit(y)][x,y−lowbit(y)]中最大值与[y-lowbit(y)+1,y][y−lowbit(y)+1,y]中的最大值，再求这两者的最大值。
稍微细心一点，就可以发现 [y-lowbit(y)+1,y][y−lowbit(y)+1,y] 就是tree[y]tree[y] （可以自己口模一下哦）。
于是，问题就转化为：求 [x,y-lowbit(y)][x,y−lowbit(y)]中最大值 与 tree[y]tree[y]的最大值。
2、y-lowbit(y) < xy−lowbit(y)<x
在这种情况下，我们直接把 a[y]a[y]（第yy个输入的数据）给剥离出来，于是原问就变成了：求 [x,y-1][x,y−1]中最大值 与 a[y]a[y] 的最大值。
好了，讨论完了。显而易见，我们把一个问题拆分成了两个子问题。这样做有什么好处？
好处就在于：我们可以用递归解决问题了！
由于我们拆分了原问题，所以不断递归的过程中，区间会越来越小。
递归到某一层时，x == yx==y，这个时候返回 a[x]a[x] 或 a[y]a[y] 就行了。（毕竟 x == yx==y时，区间[x,y][x,y]就只有a[x]a[x]这一个数据了）
所以我们就完成了这个过程（完全找不到区间和树状数组的影子了喂...）
int _findmax(int x, int y)//区间查询最大值
{
if(y > x)//区间长度不为1就拆分
{
if(y - lowbit(y) > x) return max(tree[y], _findmax(x, y - lowbit(y)));//情况1
else return max(a[y], _findmax(x, y - 1));//情况2
}
return a[x];
}
4、合并代码
建树和查找都做完了，就可以合并代码了。
#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
using namespace std;
int n, m;
int a[100005] ,treex[100005];
int lowbit(int x)//求lowbit:2进制下末尾0的个数。可表示tree中包含数据数量
{
return x & -x;
}
void _add(int x, int k)//建树QAQ
{
for(;x <= n; x += lowbit(x))
treex[x] = max(treex[x], k);
}
int _findmax(int x, int y)//区间查询最大值
{
if(y > x)
{
if(y - lowbit(y) > x) return max(treex[y], _findmax(x, y - lowbit(y)));
else return max(a[y], _findmax(x, y - 1));
}
return a[x];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++)
{
scanf("%d", &a[i]);
_add(i, a[i]);
}
for(int i = 1; i <= m; i ++)
{
int l, r;
scanf("%d%d", &l, &r);
cout << _findmax(l, r) << endl;
}
return 0;
}
好了这篇题解到这里就结束了。
那是不可能的！
你交这篇题解上去，妥妥地被TT飞。
当然我们是不可能抛弃树状数组de。
于是我参照了某位毒瘤（lxl）的博客，就是这个
（真不愧是毒瘤！）
于是我们按照上面说的进行常数优化。
由于本题输入和输出都很多，所以快读和快写都是妥妥安排上的。
再者，代码里函数调用次数很多，因为都需要递归，直接加inlineinline。
最后，在循环里加registerregister 食用即可。
其他的我就没有再用了。因为已经可以卡过去了
直接从超时代码变成300ms+300ms+（数据最大的一个点）
最终代码
#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
using namespace std;
int n, m;
int a[100005] ,tree[100005];
inline int read()//读入优化 ，加 inline 进行优化
{
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
void print(int x)//输出优化（这题输出也蛮多的，所以优化一下）
{
if(x < 0) {putchar('-'); x =- x;}
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
inline int lowbit(int x)//求lowbit:2进制下末尾0的个数。可表示tree中包含数据数量
{
return x & -x;
}
inline void _add(int x, int k)//建树QAQ
{
for(;x <= n; x += lowbit(x))
tree[x] = max(tree[x], k);
}
inline int _findmax(int x, int y)//区间查询最大值
{
if(y > x)
{
if(y - lowbit(y) > x) return max(tree[y], _findmax(x, y - lowbit(y)));
else return max(a[y], _findmax(x, y - 1));
}
return a[x];
}
int main()
{
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; i ++) //加 register 进行常数优化
{
a[i] = read();
_add(i, a[i]);
}
for(register int i = 1; i <= m; i ++)
{
int l, r;
l = read(), r = read();
print(_findmax(l, r));
printf("\n");
}
return 0;
}