题解 P3865 【【模板】ST表】
stone_juice石汁 · · 题解
我为树状数组带盐
前置芝士：树状数组
不会树状数组的戳这戳这戳这QWQ
翻了下题解，发现没有树状数组来的，我就很纳闷了。
定理1、众所周知，线段树是拿来练习树状数组的（雾）。
定理2、用线段树能切ST表
结论：树状数组能切线段树 + 线段树切了ST表 = 树状数组能切ST表 √（逻辑鬼才）
所以我们来康康树状数组怎么维护区间最大值：
-
1、求
lowbit
由于是树状数组，当然需要求
这点就不过多赘述了。如果不懂就去点最上面的链接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、查询区间最大值（划重点）
上面有提到过，建树时可以直接套区间和的板子，只需要把累加改成求最值就可以了。
但是查询不行啊啊啊...这是为什么呢？
回想一下我们如何用树状数组求区间和？ 假设我们要求出
但是最大值显然不行。当然你可以试试用看能不能输出正确答案。
好吧，那我们怎么处理查询问题？？
我们分两种情况讨论：
-
1、
y-lowbit(y) > x 这种情况下，我们可以把求
[x,y] 区间的最大值拆分成两部分，先求[x,y-lowbit(y)] 中最大值与[y-lowbit(y)+1,y] 中的最大值，再求这两者的最大值。稍微细心一点，就可以发现
[y-lowbit(y)+1,y] 就是tree[y] （可以自己口模一下哦）。于是，问题就转化为：求
[x,y-lowbit(y)] 中最大值 与tree[y] 的最大值。 -
2、
y-lowbit(y) < x 在这种情况下，我们直接把
a[y] （第y 个输入的数据）给剥离出来，于是原问就变成了：求[x,y-1] 中最大值 与a[y] 的最大值。
好了，讨论完了。显而易见，我们把一个问题拆分成了两个子问题。这样做有什么好处？
好处就在于：我们可以用递归解决问题了！
由于我们拆分了原问题，所以不断递归的过程中，区间会越来越小。
递归到某一层时，
所以我们就完成了这个过程（完全找不到区间和树状数组的影子了喂...）
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;
}好了这篇题解到这里就结束了。
那是不可能的！
你交这篇题解上去，妥妥地被
当然我们是不可能抛弃树状数组de。
于是我参照了某位毒瘤（lxl）的博客，就是这个
（真不愧是毒瘤！）
于是我们按照上面说的进行常数优化。
-
由于本题输入和输出都很多，所以快读和快写都是妥妥安排上的。
-
再者，代码里函数调用次数很多，因为都需要递归，直接加
inline 。 -
最后，在循环里加
register 食用即可。
其他的我就没有再用了。因为已经可以卡过去了
直接从超时代码变成
-
最终代码
#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;
}差不多就这样了
（悄悄求赞应该没人发现沃）