Інтервальний запит менше#5084

Інтервальний запит менше (Розбір)

Алгоритм Merge tree. У кожній вершині дерева відрізків будемо зберігати додатковий масив. Вершина, що відповідає фундаментальному відрізку $[i; j]$ , містить у своєму масиві відсортований набір чисел $a_{i}, ..., a_{j}$ a_i, ..., a_j.

Побудова такого дерева займає $O (n l o g_{2} n)$ O(nlog_2n) часу, оскільки при об'єднанні двох дочірніх вершин їхні відсортовані масиви зливаються аналогічно кроку алгоритму злиття в сортуванні злиттям.

Щоб знайти кількість чисел на відрізку $[l, r]$ [l, r], які менші за $x$ , потрібно розбити цей відрізок на набір фундаментальних відрізків дерева відрізків. Для кожного з них виконується бінарний пошук у відповідному відсортованому масиві, що дозволяє визначити кількість елементів, менших за $x$ .

Оскільки відрізок $[l, r]$ [l, r] розбивається не більше ніж на $O (l o g_{2} n)$ O(log_2n) фундаментальних відрізків, а бінарний пошук у кожному з них виконується за $O (l o g_{2} n)$ O(log_2n), час обробки одного запиту становить $O (l o g_{2}^{2} n)$ O(log_2^2n).

Приклад

Реалізація алгоритму

Оголосимо дерево відрізків. У кожній його вершині будемо зберігати масив чисел.

vector\u003cvector\u003cint\u003e \u003e SegTree;

Вхідні числа зберігаємо в масиві $a$ .

vector\u003cint\u003e a;

Функція BuildTree будує дерево відрізків за масивом $a$ . Відсортований масив у кожній вершині формується шляхом злиття масивів її дочірніх вершин за час $O (n)$ за допомогою функції merge.

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++

Функція Query підраховує кількість чисел на відрізку $[l, r]$ [l, r], значення яких менші за $x$ . Для кожного фундаментального відрізка $[l e f t; r i g h t]$ [left; right] за допомогою функції $l o w er_b o u n d$ lower\_bound знаходимо кількість чисел, менших за $x$ .

int Query(int v, int lpos, int rpos, int left, int right, int x)
{
  if (left \u003e right) return 0;
  if ((lpos == left) \u0026\u0026 (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++

Основна частина програми. Читаємо вхідний масив чисел.

scanf("%d",\u0026n);
a.resize(n + 1);
for(i = 1; i \u003c= n; i++)
  scanf("%d",\u0026a[i]);

Будуємо дерево відрізків за масивом $a$ .

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

Послідовно обробляємо $q$ запитів.

scanf("%d",\u0026q);
for(i = 0; i \u003c q; i++)
{
  scanf("%d %d %d",\u0026l,\u0026r,\u0026x);
  printf("%d\n",Query(1,1,n,l,r,x));
}