Skip to content

SQRT Decomposition

Square Root Decomposition algoritması dizi üzerinde \(\mathcal{O}(\sqrt{N})\) zaman karmaşıklığında sorgu yapabilmemize ve \(\mathcal{O}(1)\) zaman karmaşıklığında ise değişiklik yapabilmemize olanak sağlayan bir veri yapsıdır.

Yapısı ve Kuruluşu

Dizinin elemanları her biri yaklaşık \(\mathcal{O}(\sqrt{N})\) uzunluğunda bloklar halinde parçalanır. Her bir blokun cevabı ayrı ayrı hesaplanır ve bir dizide saklanır.

Blokların Cevapları \(21\) \(13\) \(50\) \(32\)
Dizideki Elemanlar \(3\) \(6\) \(2\) \(10\) \(3\) \(1\) \(4\) \(5\) \(2\) \(7\) \(37\) \(4\) \(11\) \(6\) \(8\) \(7\)
Elemanların İndeksleri \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\) \(11\) \(12\) \(13\) \(14\) \(15\) \(16\)
Örnek bir dizi üzerinde toplam sorgusu için kurulmuş SQRT Decompostion veri yapısı. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void build() {
    for (int i = 1; i <= n; i++) {
        if (i % sq == 1) { // sq = sqrt(n)
            t++;           // yeni blok baslangici.
            st[t] = i;     // t.blok i indisli elemanda baslar.
        }
        fn[t] = i;      // t.blokun bitisini i indisli eleman olarak guncelliyoruz.
        wh[i] = t;      // i indeksli eleman t.blogun icinde.
        sum[t] += a[i]; // t. blokun cevabina i indeksli elemani ekliyoruz.
    }
}

Sorgu Algoritması

Herhangi bir \([l,r]\) aralığı için sorgu algoritması sırası ile şu şekilde çalışır:

  1. Cevabını aradığımız aralığın tamamen kapladığı blokların cevabını cevabımıza ekliyoruz.
  2. Tamamen kaplamadığı bloklardaki aralığımızın içinde olan elemanları tek tek gezerek cevabımıza ekliyoruz.

Cevabını aradığımız aralığın kapsadığı blok sayısı en fazla \(\sqrt{N}\) olabileceğinden \(1.\) işlem en fazla \(\sqrt{N}\) kez çalışır. Tamamen kaplamadığı ancak bazı elemanları içeren en fazla \(2\) adet blok olabilir. (Biri en solda diğeri en sağda olacak şekilde.) Bu \(2\) blok için de gezmemiz gereken eleman sayısı maksimum \(2\sqrt{N}\) olduğundan bir sorgu işleminde en fazla \(3\sqrt{N}\) işlem yapılır, dolayısıyla sorgu işlemimiz \(\mathcal{O}(\sqrt{N})\) zaman karmaşıklığında calışır.

Blokların Cevapları \(21\) \(13\) \(50\) \(32\)
Dizideki Elemanlar \(3\) \(6\) \(2\) \(10\) \(3\) \(1\) \(4\) \(5\) \(2\) \(7\) \(37\) \(4\) \(11\) \(6\) \(8\) \(7\)
Elemanların İndeksleri \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\) \(10\) \(11\) \(12\) \(13\) \(14\) \(15\) \(16\)
Örnek dizideki \([3,13]\) aralığının cevabını \(2.\) ve \(3.\) blokların cevapları ile \(3,4\) ve \(11\) indeksli elemanların toplanmasıyla elde edilir. 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// [l,r] araligindaki elemanlarin toplamini hesaplayan fonksiyon.
int query(int l, int r) {
    int res = 0;

    if (wh[l] == wh[r]) { // l ve r ayni blogun icindeyse
        for (int i = l; i <= r; i++)
            res += a[i];
    } else {
        for (int i = wh[l] + 1; i <= wh[r] - 1; i++)
            res += sum[i]; // tamamen kapladigimiz bloklarin cevaplarini ekliyoruz.

        // tamamen kaplamadigimiz bloklardaki araligimiz icindeki
        // elemanlarin cevaplarini ekliyoruz.

        for (int i = st[wh[l]]; i <= fn[wh[l]]; i++)
            if (i >= l && i <= r)
                res += a[i];

        for (int i = st[wh[r]]; i <= fn[wh[r]]; i++)
            if (i >= l && i <= r)
                res += a[i];
    }

    return res;
}

Eleman Güncelleme Algoritması

Herhangi bir elemanın değerini güncellerken o elemanı içeren blokun değerini güncellememiz yeterli olacaktır. Dolayısıyla güncelleme işlemimimiz \(\mathcal{O}(1)\) zaman karmaşıklığında çalışır.

1
2
3
4
5
6
void update(int x, int val) {
    // x indeksli elemanin yeni degerini val degerine esitliyoruz.
    sum[wh[x]] -= a[x];
    a[x] = val;
    sum[wh[x]] += a[x];
}

SQRT Decomposition veri yapısı ile ilgili örnek bir probleme buradan ulaşabilirsiniz.