如何有效地回答整数数组中的范围查询? [英] How to effectively answer range queries in an array of integers?

问题描述

如何有效地对整数数组进行查询和定范围?

How to effectively and range queries in an array of integers?

查询仅是一种类型，即在给定范围[a,b]的情况下，找到less than x的sum of elements(此处x是每个查询的一部分，例如形式a b x).

Queries are of one type only, which is, given a range [a,b], find the sum of elements that are less than x (here x is a part of each query, say of the form a b x).

最初，我试图从字面上看从a到b并检查当前元素是否小于x并相加.但是，由于复杂度为O(n)，所以这种方法效率很低.

Initially, I tried to literally go from a to b and check if current element is less than x and adding up. But, this way is very inefficient as complexity is O(n).

现在，我正在尝试使用段树并在合并时对数字进行排序.但是现在我的挑战是，如果我进行排序，那么我将失去整数的相对顺序.因此，当查询到来时，我无法使用排序数组从a到b获取值.

Now I am trying with segment trees and sort the numbers while merging. But now my challenge is if I sort, then I am losing integers relative order. So when a query comes, I cannot use the sorted array to get values from a to b.

推荐答案

以下是使用段树解决此问题的两种方法:

Here are two approaches to solving this problem with segment trees:

您可以使用已排序数组的分段树.

You can use a segment tree of sorted arrays.

和往常一样，段树将您的数组划分为一系列大小不同的子范围.对于每个子范围，您将存储条目的排序列表以及该排序列表的累积总和.然后，您可以使用二进制搜索在任何子范围内找到低于阈值的条目总数.

As usual, the segment tree divides your array into a series of subranges of different sizes. For each subrange you store a sorted list of the entries plus a cumulative sum of the sorted list. You can then use binary search to find the sum of entries below your threshold value in any subrange.

在给定查询时，首先要计算出覆盖[a，b]范围的O(log(n))子范围.对于这些中的每一个，您都使用O(log(n))二进制搜索.总体来说，这是O(qlog ^ 2n)的复杂性，无法回答q个查询(加上预处理时间).

When given a query, you first work out the O(log(n)) subrange that cover your [a,b] range. For each of these you use a O(log(n)) binary search. Overall this is O(qlog^2n) complexity to answer q queries (plus the preprocessing time).

您可以使用动态细分树.

You can use a dynamic segment tree.

通过段树，您可以在O(logn)时间回答从a到b的元素的总和"形式的查询，还可以修改O(logn)中的单个条目.

A segment tree allows you to answer queries of the form "Compute sum of elements from a to b" in O(logn) time, and also to modify a single entry in O(logn).

因此，如果从一个空的段树开始，则可以按升序重新插入条目.假设我们添加了所有从1到5的条目，那么我们的数组可能如下所示:

Therefore if you start with an empty segment tree, you can reinsert the entries in increasing order. Suppose we have added all entries from 1 to 5, so our array may look like:

[0,0,0,3,0,0,0,2,0,0,0,0,0,0,1,0,0,0,4,4,0,0,5,1]

(0代表大于5的条目，因此尚未添加.) 此时，您可以回答阈值为5的所有查询.

(The 0s represent entries that are bigger than 5 so haven't been added yet.) At this point you can answer any queries that have a threshold of 5.

总体而言，这将花费O(nlog(n))将所有条目添加到分段树中，使用O(qlog(q))来对查询进行排序，并花费O(qlog(n))来使用分段树来回答查询.

Overall this will cost O(nlog(n)) to add all the entries into the segment tree, O(qlog(q)) to sort the queries, and O(qlog(n)) to use the segment tree to answer the queries.

这篇关于如何有效地回答整数数组中的范围查询?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！