问题标题: 请问线段树的RMQ问题怎么写？

暴力

树状数组不好吗

可以问老师

参照Luogu3372我写得题解吧

粘网址：https://www.luogu.org/blog/user31136/solution-p3372

还是手残复制了一下：

标准的线段树模板题——区间更新。

主程序——简单判断

每次读入第一个数，若是1更新，若是2直接输出。（不讲了）

关键问题——五个函数

up(int p)

这个函数主要用于更新当前节点p的值。

节点p的子节点为2p和2p+1.

s[p]=s[2p]+s[2p+1]

down(int p, int l, int r)

首先，储存节点p的值的s[p]指a[l]+...+a[r]的数字和。

这个函数用于传递add[]数组的量。

由于是区间更新，我们不能像单点更新一样一个一个更新，而是要利用add[]来存放更新的量。

这个函数1. 下传add[p]: add[2p]+=add[p];add[2p+1]+=add[p];

2. 修改子节点2p,2p+1的值：s[2p]+=(m-l+1)add[p];s[2p+1]=(r-m)add[p];

其中m=(l+r) div 2;

这里注意一下：add[p]指l-r这个区间当中：任意add[i]都应该加add[p].其中l<=i<=r.

所以我们在更新节点时，还要用add[p]乘以它区间的长度，也就是s[2p]=(m-l+1)*add[p]了。

最后将add[p]=0;

build(int p, int l, int r)

p,l,r的意思同上。

从p开始建树。

当l==r时：到了叶子节点，读入其值。

注意：应在开始之前：add[p]=0（“洗碗”操作——归零)

然后定义m=(l+r)/2;分成两路更新，最后up(p);

update(int p, int l, int r, int x, int y, int v)

p,l,r意思同上，x,y,v表示[x,y]之间的每一个点都需要+v.

注意：add[p]不需要着急传下去，我们在查询query时也会下传。

1. 当x<=l and r<=y 时，说明[l,r]区间 包含于[x,y]中，可以直接更新。

所以：add[p]+=v;s[p]+=(r-l+1)v;return;

2. 正常更新。因为这是区间更新，我们要像线段树点更新中的查询一样，分成两路进行更新。

if x<=m then update(...) //更新2*p节点

if m<y then update(...) //更新2p+1节点

这样做是因为有可能出现x<=m<=y的情况。[x,y]被m分开，所以分子节点更新。

注意：在更新前应先下传add:down(p,l,r).

防止信息留在p的父节点p/2上。

最后更新up(p);

query(int p, int l, int r, int x, int y)

查询[x,y]区间和。

1. if x<= l && r<=y return s[p];

如果[l,r]包含于[x,y]，可以直接实用[l,r]区间的数字和，直接返回。

2. 分成两路查询。

在查询之前，应再次down(p,l,r)，理由同update.

然后定义m=(l+r)/2;

if x<=m ret+=query... //获得对于2*p及其子节点进行查询的值

if m<y ret+=query... //获得对2p+1及其子节点进行查询的值

最后返回ret.

注意：

1. 数可能很大，数组定义为long long类型（pascal中的int64);

2. 一定要在update和query中down(p,l,r),及时下传add[p]。

这是思路。

具体程序不给发啊。。

1

暴力部分分

Look!

https://www.luogu.org/blog/user31136/solution-p3372

RMQ用ST表不就行了么.

以求 RMQ 问题为例我们来深入了解一下有关线段树的性质，假设本篇文章我们的要求是求区间最小值。

由上图可知，该图中的线段树维护的是 n ＝ 8 的区间的数据，每个节点存储的是所维护区间内的最小值，该线段树的深度为 L 。通常情况下整个线段树各节点的值会存储在数组里边，因此我们需要知道线段树的节点数。假设 区间的元素个数为 n ，线段树的深度为 L ，线段树的节点数为 m 。

由上图可知三者满足的关系为：

L ＝ log n ＋1（对数以 2 为底）；即 2^(L-1) = n 

m = 2^0 + 2^1 + 2^2 + 2^3 + ......+ 2^( L - 1)

m =( 2^0 + 2^0 )+ 2^1 + 2^2 + 2^3 +...... + 2^( L-1) -1

m = (2^1 + 2^1) + 2^2 + 2^3 +......+ 2^(L-1) - 1

... ...

m = 2^(L-1) + 2^(L-1) -1

m = n + n -1

m = 2n-1

由上面的推导过程可以知道，m ＝ 2n－1是妥妥的。没求证之前，可能很多人看到线段树的图之后，都会觉得规模应该是 O（n log n），虽然不知道这种错觉的理由是什么，但是知道了一点，以后凡事都需要自己亲自验证一番才能彻底打消错误的念头。这也就意味着对线段树的初始化是O（n）的时间复杂度。

现在我们来看一下求区间最值具体是怎样实现的。首先我们知道线段树上存储的是一些固定区间的最值，因此我们要求一些自定义区间的最值时，需要同时结合线段树上的若干个连续区间的多个最值，在其中选择最小的作为最后的结果，由于将整个区间分成若干子区间分别求最值最后合并结果的方法对最后结果的正确性没有影响，因此存在实现上的可行性。那么对于自定义的一个区间，在线段树上具体需要选取哪些区间呢？我们需要选取的是能够完全被自定义区间覆盖的那些区间。对于线段树上的任何一个区间，可能执行的操作有三个：

若该区间中的所有元素均包含在自定义区间中，那么直接返回线段树上存储的该区间最值。

若该区间的所有元素中任何一个元素都不曾出现在自定义区间中，那么自定义区间的最值一定不会来自该区间，这时候返回一个不影响结果判断的值即可。

若该区间既不能被自定义区间完全包含，又存在若干元素包含在自定义区间中，那么递归的对该区间对应的两个子区间分别执行这三个判断。

大概思路就是如此。

虽然将普通区间改造为线段树来维护没有增加过多的任务量，由上面的分析可以知道这么做的效果却是很惊人的，因为利用线段树求区间最值的时候，在树的每一层至多需要访问两个节点，由上至下共 L ＝ log n ＋1层，也就意味着，找到一个区间的最值需要访问的节点数 至多都不会超过 2 ＊ L － 1 ，因此查找一次区间最值时间复杂度稳定在 O（ log n）的时间复杂度，这可是个惊人的发现呢。 

线段树的另一个比较有名的应用就是修改区间上某一位置的值，可以从线段树的最底层开始修改，由于在任何一层每个元素只可能出现在一个区间，因此修改一个值的时间复杂度恒为O（log n）。

链接: https://pan.baidu.com/s/1pKXUtGB 密码: 6tb4

so difficult！

李泽远在2020-01-05 16:01:07追加了内容

我改变主意了：

so easy！

真不会

难，不会

不会

不会

111