Interval Less Query#5084

Interval Less Query (Çözgüdiň düşündirişi)

Merge Tree algorithm. In each vertex of the segment tree store an additional array. The vertex corresponding to the fundamental segment $[i; j]$ contains in its array the sorted sequence of numbers $a_{i}, ..., a_{j}$ a_i, ..., a_j.

The construction of such a tree takes $O (n l o g_{2} n)$ O(nlog_2n) time, since when combining two child vertices their sorted arrays are merged in the same way as in the merge step of the merge sort algorithm.

To find the number of elements in the segment $[l, r]$ [l, r] that are less than $x$ , the segment is decomposed into a set of fundamental segments of the segment tree. For each of these segments, a binary search is performed in the corresponding sorted array to determine how many elements are less than $x$ .

Since the segment $[l, r]$ [l, r] can be decomposed into at most $O (l o g_{2} n)$ O(log_2n) fundamental segments, and a binary search in each of them takes $O (l o g_{2} n)$ O(log_2n) time, the processing time for a single query is $O (l o g_{2}^{2} n)$ O(log_2^2n).

Example

Algorithm implementation

Let's declare a segment tree. In each of its nodes, we'll store an array of numbers.

vector<vector<int> > SegTree;

The input numbers are stored in the array $a$ .

vector<int> a;

The function BuildTree constructs the segment tree based on the array $a$ . The sorted array in each node is formed by merging the arrays of its child nodes in $O (n)$ time using the merge function.

void BuildTree(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    SegTree[v].push_back(a[lpos]);
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(2*v, lpos, mid);
    BuildTree(2*v+1, mid+1, rpos);

    SegTree[v].resize(rpos - lpos + 1);
    merge(SegTree[2*v].begin(), SegTree[2*v].end(), 
          SegTree[2*v+1].begin(), SegTree[2*v+1].end(), 
          SegTree[v].begin());
  }
}

C++

The function Query counts the number of elements in the segment $[l, r]$ [l, r] that are less than $x$ . For each fundamental segment $[l e f t; r i g h t]$ [left; right], the number of elements less than $x$ is determined using the $l o w er_b o u n d$ lower\_bound function.

int Query(int v, int lpos, int rpos, int left, int right, int x)
{
  if (left > right) return 0;
  if ((lpos == left) && (rpos == right))
    return lower_bound(SegTree[v].begin(), SegTree[v].end(), x) – 
           SegTree[v].begin();

  int mid = (lpos + rpos) / 2;
  return Query(2*v, lpos, mid, left, min(mid, right), x) +
         Query(2*v+1, mid+1, rpos, max(left, mid+1), right, x);
}

C++

The main part of the program. Read the input array of integers.

scanf("%d",&n);
a.resize(n + 1);
for(i = 1; i <= n; i++)
  scanf("%d",&a[i]);

Build the segment tree based on the array $a$ .

SegTree.resize(4*n);
build(1,1,n);

Process the $q$ queries sequentially.

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d %d %d",&l,&r,&x);
  printf("%d\n",Query(1,1,n,l,r,x));
}