İntervalda kiçik ədədlərin sorğusu#5084

İntervalda kiçik ədədlərin sorğusu (Həll təhlili)

Merge tree alqoritmi. Seqment ağacının hər bir təpəsində əlavə massiv saxlayacağıq. $[i; j]$ fundamental parçasına uyğun gələn təpə öz massivində $a_{i}, ..., a_{j}$ a_i, ..., a_j ədədlərinin sıralanmış çoxluğunu saxlayır.

Belə ağacın qurulması $O (n l o g_{2} n)$ O(nlog_2n) vaxt aparır, çünki iki törəmə təpənin birləşdirilməsi zamanı onların sıralanmış massivləri, sıralama-birləşdirmə (merge sort) alqoritminin birləşdirmə addımına oxşar şəkildə birləşdirilir.

$[l, r]$ [l, r] parçasında $x$ -dən kiçik olan ədədlərin sayını tapmaq üçün bu parça seqment ağacının fundamental parçalar toplusuna bölünməlidir. Onların hər biri üçün müvafiq sıralanmış massivdə ikili axtarış (binary search) icra olunur ki, bu da $x$ -dən kiçik olan elementlərin sayını müəyyən etməyə imkan verir.

$[l, r]$ [l, r] parçası ən çoxu $O (l o g_{2} n)$ O(log_2n) fundamental parçaya bölündüyündən, onların hər birində isə ikili axtarış $O (l o g_{2} n)$ O(log_2n) vaxtda icra olunduğundan, bir sorğunun işlənmə vaxtı $O (l o g_{2}^{2} n)$ O(log_2^2n) təşkil edir.

Nümunə

Alqoritmin realizasiyası

Seqment ağacını elan edək. Onun hər bir təpəsində ədədlər massivini saxlayacağıq.

vector\u003cvector\u003cint\u003e \u003e SegTree;

Giriş ədədlərini $a$ massivində saxlayırıq.

vector\u003cint\u003e a;

BuildTree funksiyası $a$ massivi əsasında seqment ağacını qurur. Hər təpədəki sıralanmış massiv onun törəmə təpələrinin massivlərinin merge funksiyası vasitəsilə $O (n)$ vaxtda birləşdirilməsi yolu ilə formalaşdırılır.

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 funksiyası $[l, r]$ [l, r] parçasında qiymətləri $x$ -dən kiçik olan ədədlərin sayını hesablayır. Hər bir $[l e f t; r i g h t]$ [left; right] fundamental parçası üçün $l o w er_b o u n d$ lower\_bound funksiyası vasitəsilə $x$ -dən kiçik olan ədədlərin sayını tapırıq.

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

Proqramın əsas hissəsi. Giriş ədədlər massivini oxuyuruq.

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

$a$ massivi əsasında seqment ağacını qururuq.

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

$q$ sorğusunu ardıcıl olaraq işləyirik.

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));
}