algorithm - 给定范围内数组的两个元素之间的最大差异

Question

我需要在给定范围 [i,j] 中有效地找到最大 {S} 使得 S=(A[i]-A[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

Answer 1

这个问题对我来说真的很有趣，现在我不知道我的方法是否完全正确，但我试了一下，它给了我当前输入的正确结果。

因此，根据我的方法，我保留了一个线段树来保留所有范围的最大值，并保留了另一个线段树来存储左侧最大值与右侧最大值之间的差值。

这里要注意一点，我之所以这样做是因为我们需要 A[i] - A[j] 并且 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() 为左树最大值与右树最大值之间的差异构建线段树。

如果我在当前方法中犯了任何错误，请告诉我。

希望这对您有所帮助!