Silinmələr ilə XOR əsası

Ön söz

Bu məqalədə xətti cəbrdən terminlər istifadə olunur. Əgər bu terminləri başa düşürsünüzsə, bu bölməni keçə bilərsiniz.

Giriş

Gəlin aşağıdakı yaxşı bilinən problemi xatırlayaq:

Bu problemi necə həll etməyi buradan öyrənə bilərsiniz.

Bu məqalədə isə, $S$ çoxluğundan tam ədədlərin silinmə sorğularının da olduğu daha mürəkkəb bir problemi nəzərdən keçirəcəyik. Üstəlik, növbəti sorğunu yalnız əvvəlki sorğuya cavab verdikdən sonra alırıq (yəni, problem "onlayn" həll edilməlidir).

Başlanğıc problemi hər bir sorğu üçün $O(m)$ zaman sərfində həll etmək mümkündür, lakin biz silinmələr olan problemi $O(m^2)$ zaman sərfində həll etməyi öyrənəcəyik.

Struktur

Silinmələrlə olan problemdə, əlavə etdiyimiz tam ədədin mövcud əsas elementlərinin $\mathrm{xor}$-u ilə ifadə olunması qeyri-müəyyənlik yaradır.

$S$-ə əlavə olunan hər bir tam ədədi effektiv şəkildə saxlamaq istəyirik, buna görə də tək bir əsası deyil, hər biri əvvəlcə boş olan, XOR əsaslarının ardıcıllığını $X_n$ ($n\ge 1$) saxlayacağıq.

$v$ tam ədədini $S$-ə əlavə etmək

Gəlin $v\ne 0$ yeni tam ədədini $S$ çoxluğuna necə əlavə edəcəyimizi nəzərdən keçirək:

1. İlk əsasdan başlayaraq ardıcıllıqları tədricən nəzərdən keçirəcəyik. Gəlin $i$-ni cari nəzərdən keçirdiyimiz əsasın tam ədədi adlandıraq;

2. Əgər $v\notin \mathrm{span}(X_i)$, sadəcə $v$-i $X_i$-yə əlavə edirik və proseduru bitiririk;

3. Əks halda, $v\in \mathrm{span}(X_i)$, bu halda onu əsasa əlavə edə bilmərik, lakin bu tam ədədi haradasa saxlamaq istəyirik. Bu səbəbdən $i$-ni $1$ vahid artırıb addım $2$-yə qayıdırıq.

Başqa sözlə, $v\notin \mathrm{span}(X_i)$ olan minimal $i$-ni tapırıq və $v$-i $X_i$-yə əlavə edirik. Əgər bu alqoritmi birbaşa tətbiq etsək, ən pis halda o, $O(|S|)$ zaman sərfində işləyəcək ki, bu da olduqca səmərəsizdir.

Bu alqoritmi təkmilləşdirəcəyik. İlk növbədə, $X_n$ ardıcıllığının bəzi xüsusiyyətlərini nəzərdən keçirək:

Qalan tərcümə də bu tərzdə davam etdirilə bilər. Hər bir texniki termin və mətnin formatı dəyişdirilmədən qorunmalıdır ki, oxucu orijinal məqalənin strukturu və məntiqi ilə asanlıqla tanış olsun.