给定范围内数组的两个元素之间的最大差值
给定范围内数组的两个元素之间的最大差值
提问于 2017-07-21 19:46:53
我需要有效地找到max{S}，使得S=(Ai-Aj)在给定的范围i，j中。除了暴力解决方案之外，我找不到解决方案，在这种方案中，对于每个查询，从索引i到索引j迭代数组并找到解决方案。我正在考虑使用两个分段树，一个用于查找给定范围内的最小值，另一个用于查找给定范围内的最大值，但由于有一个额外的约束，例如i<=j，所以这并不是在所有情况下都能给出正确的答案。
Constraint:i<=j
n- number of elements in an array (n<=10^6)
q- number of Queries (q<=10^5)
Example:
Input
5
2 8 4 9 7
2
0 4
2 4
Output
4
2
Explanation:
Input consists of an array with 5 elements and then 2 queries.
1) In the range [0,4] - (8-4) = 4 is the answer
2) In the range [2,4] - (9-7) = 2 is the answer回答 1
Stack Overflow用户
发布于 2017-07-21 23:50:39
这个问题对我来说似乎真的很有趣，现在我不知道我的方法是否完全正确，但我尝试了一下，它给出了当前输入的正确结果。
因此，根据我的方法，我保留了一个分段树来保存所有范围的最大值，另一个分段树存储了左侧的最大值-右侧的最大值之间的差值。
这里需要注意的一点是，我这样做是因为我们需要Ai - Aj和i- <= j，所以如果我们继续存储左范围的最大值和右范围的最大值，那么我们总是会得到差值，也就是i- <= j。
请看一下我的代码，以便更好地理解这一点。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5; // limit for array size
int n; // array size
int t[2 * N];
int t_ans[2*N];
void build1() { // build the tree
for (int i = n - 1; i > 0; --i) t[i] = max(t[i<<1],t[i<<1|1]);
}
void build2() { // build the tree
for (int i = n - 1; i > 0; --i) t_ans[i] = t[i<<1] - t[i<<1|1];
}
void modify(int p, int value) { // set value at position p
for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
}
int query(int l, int r) { // sum on interval [l, r)
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) res = max(res,t[l++]);
if (r&1) res = max(res,t[--r]);
}
return res;
}
int query2(int l, int r) { // sum on interval [l, r)
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) res = max(res, t_ans[l++]);
if (r&1) res = max(res, t_ans[--r]);
}
return res;
}
int main() {
cin>>n;
for (int i = 0; i < n; ++i) {
scanf("%d", t + n + i);
}
build1();
build2();
/*
For testing purpose only
for(int i=0; i<2*n; i++) {
cout<<t[i]<<" ";
}
cout<<endl;
for(int i=0; i<2*n; i++) {
cout<<t_ans[i]<<" ";
}
cout<<endl;
*/
int q;
cin>>q;
for(int i=0; i<q; i++) {
int l,r;
cin>>l>>r;
cout<<query2(l,r+1)<<endl;
}
return 0;
}我保留了两个分段树，一个用于存储最大范围值，名为t，另一个用于存储最大差值，存储在t_ans中。
现在我调用了两个不同的构建方法，build1()为最大值构建段树，build2()为左树的最大值与右树的最大值之间的差值构建段树。
如果我在当前的方法中犯了任何错误或错误，请让我知道。
希望这能有所帮助！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/45236879
复制相关文章
相似问题
腾讯云开发者
