查找具有负值的最大数组索引

Question

给定一个正元素数组（基于 1 的索引），您必须处理两种类型的查询：

(V) 求 1:V 范围内的数字之和（包括）
(V, X) 从范围 1:V 中的所有值中减去数字 X 并报告范围 1:V 中的最大索引 i 使得该索引处的值为负数，其中如果不存在此类索引，则此查询的答案为 0。

我可以使用分域树或线段树进行第一个查询，但我如何支持第二个查询？我已经尝试过每次查询的 O(n) 时间方法，只是检查 1...V 范围内的每个元素，但它超时了。我需要在大小为 10^5 的数组上处理 10^5 个这样的查询。

Answer 1

最直接的方法是通过简单地搜索数组在 O(n) 时间内找到元素，如下所示：

arr = [0,5,2,3,10]
largest_i = -1
X = 7
for i in range(len(arr)):
  if arr[i]-X<0:
    largest_i = i
largest_i+1 #Your answer (shifting from a 0-based to a 1-based index)

鉴于数组的大小和时间限制，这应该适用于任何编译语言和大多数解释语言。

编辑

我的观点是正确的（很明显 10^10 的最坏情况非常糟糕）。既然你说超时了，这里有一个更复杂的方法。

创建一个AVL树，或者另一个支持插入和删除的自平衡二叉树。
创建具有属性 value 和 index 的关键项。 value 是项目的值，而 index 是项目在平面数组中的位置。
根据 index.
向树中添加项目，使其平衡 value，但删除基于 index 的项目。
更新平面阵列时，相应地更新树。
要回答查询 2，请按顺序遍历树直到 value-X>=0。 Return 最后一个节点的 index 这是错误的。

树的插入和删除都在O(log n)中，而中序遍历的最坏情况是O(n) ，但保证只检查可能为负的元素。

一个可能的实现如下：

#include <map>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cstdlib>
#include <cassert>

class MagicArray {
 private:
  typedef std::multimap<int, int> arr_idx_t;
  std::vector<int> arr; //Array of possibly negative integers
  arr_idx_t arr_sorted; //Self-balancing tree of (Integer, Index) pairs
  std::unordered_map<int, arr_idx_t::iterator> arr_idx; //Hash table linking Index to a (Integer, Index)
  void indexElement(const int idx){
    auto ret = arr_sorted.emplace(arr.at(idx),idx);
    arr_idx[idx] = ret;
  }
 public:
  void insert(const int i){
    arr.emplace_back(i);
    const auto idx = arr.size()-1; //Index of most recently inserted element
    indexElement(idx);
  }
  void alter(const int idx, const int newval){
    arr.at(idx) = newval;
    arr_sorted.erase(arr_idx[idx]); //Remove old value from tree
    indexElement(idx);
  }
  int findMatch(const int X){
    //The next two lines reduce run-time from 3s to 0.031s
    if(arr_sorted.rbegin()->first-X<0) //Even largest element is less than zero
      return arr.size();

    int foundi = -1;
    for(const auto &kv: arr_sorted){
      if(kv.first-X<0){
        foundi = std::max(foundi,kv.second);
      } else {
        break;
      }
    }
    return foundi+1;
  }
};

int main(){
  assert(RAND_MAX>10000000); //Otherwise code below will not work

  MagicArray ma;
  for(unsigned int i=0;i<10000;i++)
    ma.insert(rand()%10000);

  for(unsigned int i=0;i<10000;i++){
    ma.alter(rand()%10000,rand()%10000);
    ma.findMatch(rand()%1000000);
  }
}

如果您省略 findMatch 的前两行代码，这在我的 Intel(R) Core(TM) i5 CPU M480@2.67GHz 上需要 3 秒，在 Intel 上需要 2.359 秒（ R) Xeon(R) CPU E5-2680v3@2.50GHz 在超级计算机上。

如果您包含 findMatch 的前两行代码，那么两台机器上的代码都需要 <0.035 秒。

这就是考虑值的范围非常重要的原因。你说数组包含 [0,10⁵] 范围内的值，而 X 在 [0,10⁷] 范围内，这意味着 X 所取值的 99% 将大于数组中的任何值因此答案就是数组的大小。

所以诀窍是使用成本较低的检查来查看我们是否简单地知道答案，如果不知道，则执行成本更高的搜索。

Answer 2

使用线段树，使得每个节点存储其范围内的最小值以及其范围内元素的总和。第一次查询可以直接在 logn 时间复杂度内完成。对于第二个查询，首先从范围内的每个元素中减去给定的值（再次登录），然后查询最右边小于 0 的值（也登录）。

编辑：更好的解释

所以首先构建一个线段树，使得叶子存储数组中的原始值。每个其他节点都使用两个值构建：totalsum 和 minval。使用此等式轻松构建：

segment_tree[id].minval = min(segment_tree[id*2].minval, segment_tree[id*2+1].minval)
segment_tree[id].totalsum = segment_tree[id*2].totalsum + segment_tree[id*2+1].totalsum

构建需要 O(n)。

查询 A：查找某个范围内的总和很容易，只需找到与您的查询范围相关的最高范围并将它们相加即可。每个查询的时间 O(logn)。

查询 B：将此查询分成两个操作：

A) 从范围中减去 X：假设您从某个范围 [a,b] 中减去 X。所以 [a,b] 的总和变为 old_totalsum[a,b] - (b+1-a)*X，新的最小值变为 old_minval[a,b] - X。关键是您再次仅在查询范围内的段树的最顶端范围内执行此操作，以便该操作仅需 logn 复杂度。这项技术还有更多内容，如果您还不熟悉它（称为惰性传播），您应该在线阅读它。

B) 检查值 < 0 的最右边索引：在线段树的根上开始查询。右边的最小值child < 0？然后去那里。 else 是 leftchild < 0 的最小值吗？然后向左走child。如果 children 的 minval > 0，return -1。一旦到达一片叶子，只需 return 叶子对应的索引。所以你沿着树的高度遍历一次，再次 O(logn).

所以程序的总复杂度为 O(n + Q.logn)，其中 Q 是查询的数量。

查找具有负值的最大数组索引

Finding the largest array index with negative value

arrays

algorithm

tree

bit

segment