使用Fenwick树在L到R范围内大于K的元素数（离线查询）

2021年5月15日18:32:01 发表评论 1,020 次浏览

本文概述

先决条件： 芬威克树(二叉索引树)

给定一个由N个数字组成的数组, 以及多个查询, 其中每个查询将包含三个数字(l, r和k)。任务是计算子数组[L, R]中大于K的数组元素的数量。

例子：

Input:  n=6                                           
         q=2                                           
         arr[ ] = { 7, 3, 9, 13, 5, 4 }  
         Query1: l=1, r=4, k=6
         Query2: l=2, r=6, k=8

Output: 3
         2

For the first query, [7, 3, 9, 13] represents the 
subarray from index 1 till 4, in which there are 
3 numbers which are greater than k=6 that are {7, 9, 13}.

For the second query, there are only 
two numbers in the query range which
are greater than k.

天真的方法

是通过简单地从索引l遍历到r遍历数组来查找每个查询的答案, 并在数组元素大于k时保持对计数加1。

时间复杂度：O(n * q)

一个更好的方法

使用合并排序树。在这种方法中, 构建一个分段树, 在每个节点上以一个矢量包含一个包含子范围内所有元素(按排序顺序)的向量。使用段树回答每个查询, 其中可以使用二进制搜索来计算子范围在查询范围内的每个节点中有多少个数字大于k。

时间复杂度：

O(q * log(n)* log(n))

An高效方法是使用离线查询解决问题, 芬威克树。步骤如下：

  • 首先将所有数组元素和查询存储在同一数组中。为此, 我们可以创建一个自结构或类。
  • 然后按降序对结构数组进行排序(如果发生冲突, 查询将首先出现, 然后是数组元素)。
  • 再次处理整个结构数组, 但在此之前创建另一个BIT数组(二叉索引树), 其query(i)函数将返回数组中存在的所有元素的计数, 直到第i个索引为止。
  • 最初, 用0填充整个数组。
  • 创建一个答案数组, 其中存储每个查询的答案。
  • 处理结构数组。
  • 如果它是一个数组元素, 则从该元素的索引中用+1更新BIT数组。
  • 如果是查询, 则减去查询(r)–查询(l-1)这就是该查询的答案, 该答案将存储在答案数组中与查询编号相对应的索引处。
  • 最后输出答案数组。

此处的主要观察结果是, 由于结构的数组已按降序排序。每当我们遇到任何查询时, 只有大于" k"的元素才构成BIT数组中的计数, 这是需要的答案。

下面是程序中使用的结构的说明：

位置：存储查询顺序。如果是数组元素, 则保留为0。L：存储查询子数组的起始索引。如果是数组元素, 则它也为0。R：存储查询子数组的结尾Idex。对于数组元素, 它用于存储元素在数组中的位置。 Val：存储查询的" k"和所有数组元素。

下面是上述方法的实现：

C ++

//C++ program to print the number of elements
//greater than k in a subarray of range L-R.
#include <bits/stdc++.h>
using namespace std;
  
//Structure which will store both
//array elements and queries.
struct node {
     int pos;
     int l;
     int r;
     int val;
};
  
//Boolean comparator that will be used
//for sorting the structural array.
bool comp(node a, node b)
{
     //If 2 values are equal the query will
     //occur first then array element
     if (a.val == b.val)
         return a.l> b.l;
  
     //Otherwise sorted in descending order.
     return a.val> b.val;
}
  
//Updates the node of BIT array by adding
//1 to it and its ancestors.
void update( int * BIT, int n, int idx)
{
     while (idx <= n) {
         BIT[idx]++;
         idx += idx & (-idx);
     }
}
//Returns the count of numbers of elements
//present from starting till idx.
int query( int * BIT, int idx)
{
     int ans = 0;
     while (idx) {
         ans += BIT[idx];
  
         idx -= idx & (-idx);
     }
     return ans;
}
  
//Function to solve the queries offline
void solveQuery( int arr[], int n, int QueryL[], int QueryR[], int QueryK[], int q)
{
     //create node to store the elements
     //and the queries
     node a[n + q + 1];
     //1-based indexing.
  
     //traverse for all array numbers
     for ( int i = 1; i <= n; ++i) {
         a[i].val = arr[i - 1];
         a[i].pos = 0;
         a[i].l = 0;
         a[i].r = i;
     }
  
     //iterate for all queries
     for ( int i = n + 1; i <= n + q; ++i) {
         a[i].pos = i - n;
         a[i].val = QueryK[i - n - 1];
         a[i].l = QueryL[i - n - 1];
         a[i].r = QueryR[i - n - 1];
     }
  
     //In-built sort function used to
     //sort node array using comp function.
     sort(a + 1, a + n + q + 1, comp);
  
     //Binary Indexed tree with
     //initially 0 at all places.
     int BIT[n + 1];
  
     //initially 0
     memset (BIT, 0, sizeof (BIT));
  
     //For storing answers for each query( 1-based indexing ).
     int ans[q + 1];
  
     //traverse for numbers and query
     for ( int i = 1; i <= n + q; ++i) {
         if (a[i].pos != 0) {
  
             //call function to returns answer for each query
             int cnt = query(BIT, a[i].r) - query(BIT, a[i].l - 1);
  
             //This will ensure that answer of each query
             //are stored in order it was initially asked.
             ans[a[i].pos] = cnt;
         }
         else {
             //a[i].r contains the position of the
             //element in the original array.
             update(BIT, n, a[i].r);
         }
     }
     //Output the answer array
     for ( int i = 1; i <= q; ++i) {
         cout <<ans[i] <<endl;
     }
}
  
//Driver Code
int main()
{
     int arr[] = { 7, 3, 9, 13, 5, 4 };
     int n = sizeof (arr) /sizeof (arr[0]);
  
     //1-based indexing
     int QueryL[] = { 1, 2 };
     int QueryR[] = { 4, 6 };
  
     //k for each query
     int QueryK[] = { 6, 8 };
  
     //number of queries
     int q = sizeof (QueryL) /sizeof (QueryL[0]);
  
     //Function call to get
     solveQuery(arr, n, QueryL, QueryR, QueryK, q);
  
     return 0;
}

Python3

# Python program to print the number of elements
# greater than k in a subarray of range L-R.
  
# Structure which will store both
# array elements and queries.
class node:
     def __init__( self ):
         self .pos = 0
         self .l = 0
         self .r = 0
         self .val = 0
  
# Updates the node of BIT array by adding
# 1 to it and its ancestors.
def update(BIT: list , n: int , idx: int ):
     while idx <= n:
         BIT[idx] + = 1
         idx + = idx & - idx
  
# Returns the count of numbers of elements
# present from starting till idx.
def query(BIT: list , idx: int ) -> int :
     ans = 0
     while idx:
         ans + = BIT[idx]
         idx - = idx & - idx
     return ans
  
# Function to solve the queries offline
def solveQuery(arr: list , n: int , QueryL: list , QueryR: list , QueryK: list , q: int ):
  
     # create node to store the elements
     # and the queries
     a = [ 0 ] * (n + q + 1 )
     for i in range (n + q + 1 ):
         a[i] = node()
      
     # 1-based indexing
  
     # traverse for all array numbers
     for i in range ( 1 , n + 1 ):
         a[i].val = arr[i - 1 ]
         a[i].pos = 0
         a[i].l = 0
         a[i].r = i
  
     # iterate for all queries
     for i in range (n + 1 , n + q + 1 ):
         a[i].pos = i - n
         a[i].val = QueryK[i - n - 1 ]
         a[i].l = QueryL[i - n - 1 ]
         a[i].r = QueryR[i - n - 1 ]
  
     # In-built sorted function used to
     # sort node array using comp function.
     a = [a[ 0 ]] + sorted (a[ 1 :], key = lambda k: (k.val, k.l), reverse = True )
  
     # Binary Indexed tree with
     # initially 0 at all places.
     BIT = [ 0 ] * (n + 1 )
  
     # For storing answers for 
     # each query( 1-based indexing ).
     ans = [ 0 ] * (q + 1 )
  
     # traverse for numbers and query
     for i in range ( 1 , n + q + 1 ):
         if a[i].pos ! = 0 :
  
             # call function to returns answer for each query
             cnt = query(BIT, a[i].r) - query(BIT, a[i].l - 1 )
  
             # This will ensure that answer of each query
             # are stored in order it was initially asked.
             ans[a[i].pos] = cnt
         else :
  
             # a[i].r contains the position of the
             # element in the original array.
             update(BIT, n, a[i].r)
  
     # Output the answer array
     for i in range ( 1 , q + 1 ):
         print (ans[i])
  
# Driver Code
if __name__ = = "__main__" :
  
     arr = [ 7 , 3 , 9 , 13 , 5 , 4 ]
     n = len (arr)
  
     # 1-based indexing
     QueryL = [ 1 , 2 ]
     QueryR = [ 4 , 6 ]
  
     # k for each query
     QueryK = [ 6 , 8 ]
  
     # number of queries
     q = len (QueryL)
  
     # Function call to get
     solveQuery(arr, n, QueryL, QueryR, QueryK, q)
  
# This code is contributed by
# sanjeev2552

输出如下：

3
2

时间复杂度：O(N * log N)其中N =(n + q)

什么是离线查询？

在某些问题中, 很难以任何随机顺序回答查询。因此, 与其单独回答每个查询, 不如存储所有查询, 然后对它们进行相应排序, 以有效地计算出它们的答案。存储所有答案, 然后按照最初给出的顺序输出。

这种技术称为离线查询.

注意：代替分域树, 也可以使用段树, 其中段树的每个节点将存储在该迭代之前插入的元素数。更新和查询功能将更改, 其余实现将保持不变。

脱机查询的必要条件：仅当一个查询的答案不取决于先前查询的答案时, 才可以使用此技术, 因为排序后查询的顺序可能会更改。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: