Editorial unofficial: pohon dinamis dengan biaya penggabungan linear

Status dan cakupan

Tulisan ini mendokumentasikan implementasi yang memperoleh 100/100 dalam pengujian submit yang dilaporkan. Implementasinya menggunakan dua algoritma:

• Algoritma A, untuk subtask $2$ dan $4$: dekomposisi rantai dua tingkat, AVL, cache interval dengan timestamp, dan materialisasi himpunan secara selektif.
• Algoritma B, untuk subtask $1$, $3$, dan $5$: partisi pohon menjadi cluster kecil dengan prefix himpunan di dalam setiap cluster.

Ada perbedaan penting antara tiga pernyataan berikut:

1. Setiap jawaban yang dihasilkan adalah tepat.
2. Biaya memenuhi suatu batas matematis untuk seluruh masukan legal.
3. Implementasi memperoleh skor penuh pada pengujian penilai.

Untuk Algoritma B, tulisan ini memberikan pembuktian correctness sekaligus batas eksplisit

$$ C_2\le 4158<5000. $$

Untuk Algoritma A, tulisan ini memberikan pembuktian correctness, analisis struktur data, dan pembukuan biaya yang eksak. Namun, belum ada pembuktian dalam tulisan ini bahwa implementasi tersebut selalu memenuhi

$$ C_1\le 1.5\cdot 10^8 $$

pada setiap masukan legal. Parameter materialisasi dan kebijakan cache pada bagian ini merupakan bagian dari rekayasa implementasi yang memperoleh skor penuh. Hasil tersebut tidak digunakan sebagai pengganti pembuktian batas worst-case.

Dengan demikian, tulisan ini adalah editorial lengkap mengenai mekanisme implementasi 100 poin tersebut, dengan batas analisisnya dinyatakan terbuka. Bagian Algoritma A tidak boleh dikutip sebagai teorema jaminan skor penuh worst-case.

1. Memahami model biaya

Kita mempunyai pohon berakar di simpul $1$, dengan $n$ simpul. Awalnya tersedia himpunan singleton

$$ \{1\},\{2\},\ldots,\{n\}. $$

Jika dua himpunan yang sudah tersedia saling lepas, kita boleh membuat gabungannya:

$$ A\cap B=\varnothing \quad\Longrightarrow\quad A\cup B, $$

dengan biaya

$$ \operatorname{cost}_{\mathrm{merge}}(A,B)=|A|+|B|. $$

Himpunan yang sudah dibuat tetap tersedia. Menggabungkan dua himpunan dengan hasil yang pernah dibuat sebelumnya tetap dikenai biaya jika kita benar-benar memanggil operasi penggabungan lagi.

Terdapat dua operasi pada pohon:

• $\operatorname{modify}(x,y)$: mengganti orang tua $x$ menjadi $y$.
• $\operatorname{ask}(x,y)$: melaporkan sebuah partisi himpunan simpul pada jalur $x$ ke $y$.

Jika

$$ P(x,y)=A_1\mathbin{\dot\cup}A_2\mathbin{\dot\cup}\cdots \mathbin{\dot\cup}A_k, $$

maka biaya pelaporannya adalah $k$. Simbol $\dot\cup$ menyatakan gabungan saling lepas.

Kita mengoptimalkan dua besaran:

$$ C_1 = \sum_{\text{semua merge}}(|A|+|B|) + \sum_{\text{semua query}}\#\operatorname{report}, $$

dan

$$ C_2 = \max_{\text{satu operasi setelah init}} \operatorname{cost}(\text{operasi tersebut}). $$

Biaya di dalam $\operatorname{init}$ masuk ke $C_1$, tetapi tidak masuk ke $C_2$.

Ambang skor penuh yang relevan adalah:

1.1 Tiga besaran yang harus dibedakan

Ada tiga hal berbeda:

1. waktu CPU program;
2. banyaknya pemanggilan fungsi pustaka;
3. biaya yang didefinisikan soal.

Sebuah penggabungan bisa menggunakan satu pemanggilan fungsi, tetapi menambah biaya sebesar $10^5$. Sebaliknya, ribuan operasi pointer pada struktur data dapat tidak menambah biaya soal sama sekali.

Tipe $\texttt{infoset}$ pada penilai resmi adalah handle berukuran tetap. Kita tidak boleh mengasumsikan bahwa implementasi internalnya adalah vektor simpul seperti pada grader contoh, dan tidak boleh membaca isi internalnya.

1.2 Himpunan tidak mempunyai urutan

Jawaban yang diminta adalah himpunan simpul pada jalur. Kita tidak perlu melaporkan urutan perjalanan dari $x$ menuju $y$.

Akibatnya, himpunan yang sama dapat dipakai meskipun urutan simpulnya dalam suatu representasi internal berbeda. Satu-satunya syarat saat melaporkan adalah cakupan tepat dan tidak adanya tumpang tindih.

2. Mengapa langsung memakai Link-Cut Tree belum menyelesaikan masalah?

Pada dynamic tree biasa, kita sering menyimpan agregat

$$ \operatorname{val}(u) = \operatorname{val}(\operatorname{left}(u)) \operatorname{value}(u) \operatorname{val}(\operatorname{right}(u)). $$

Jika penggabungannya berbiaya $O(1)$, sebuah rotasi dapat memperbarui agregat dalam $O(1)$.

Di soal ini, jika agregat mencakup $s$ simpul, membentuknya kembali bisa menambah biaya sebesar $\Theta(s)$.

Maka pernyataan

$$ \text{“Ada }O(\log n)\text{ rotasi, sehingga biayanya }O(\log n)\text{”} $$

tidak berlaku. Yang dihitung soal adalah ukuran himpunan pada setiap penggabungan, bukan jumlah rotasinya.

Pada rantai panjang, perubahan kecil pada auxiliary tree dapat menyebabkan pembentukan ulang beberapa himpunan besar. Inilah hambatan utama.

Prinsip yang akan kita gunakan adalah:

Perubahan representasi struktur data tidak harus langsung diikuti pembentukan ulang himpunan.

Kita boleh mengubah pointer, menyimpan metadata, dan menunda penggabungan. Saat query datang, sebuah bagian besar dapat dilaporkan menggunakan beberapa himpunan lebih kecil yang sudah tersedia.

3. Peta solusi per subtask

Implementasi 100 poin menggunakan Algoritma B juga pada subtask $1$, agar kode dapat dibagi menjadi dua cabang saja.

Untuk mempelajarinya, urutan yang nyaman adalah:

$$ \text{subtask }1 \;\longrightarrow\; \text{Algoritma B} \;\longrightarrow\; \text{rantai dinamis} \;\longrightarrow\; \text{Algoritma A}. $$

4. Subtask 1: jangan melakukan penggabungan

Untuk $n,q\le 100$, kita dapat menyimpan orang tua setiap simpul secara langsung.

Saat menerima query:

1. tandai seluruh leluhur $x$;
2. naik dari $y$ hingga menemukan leluhur pertama yang sudah ditandai;
3. simpul tersebut adalah $w=\operatorname{LCA}(x,y)$;
4. laporkan singleton pada jalur $x\to w$ dan $y\to w$, dengan $w$ dilaporkan sekali.

Modifikasi hanya mengganti satu nilai orang tua.

Tidak ada penggabungan. Setiap query menggunakan paling banyak $n$ laporan, sehingga

$$ C_1\le nq\le 10^4. $$

Waktu totalnya $O(nq)$, dengan memori $O(n)$.

Correctness langsung mengikuti fakta bahwa jalur sederhana pada pohon adalah

$$ P(x,y) =P(x,w)\cup P(y,w), $$

dan kedua bagian tersebut hanya beririsan di $w$.

5. Algoritma B: cluster kecil untuk membatasi biaya satu operasi

Bagian ini menyelesaikan subtask $3$ dan $5$ dengan jaminan eksplisit. Syarat bentuk pohon pada subtask $3$ tidak diperlukan.

Pilih batas ukuran cluster $B$. Dalam implementasi:

$$ B=64. $$

Kita mempertahankan partisi simpul pohon menjadi cluster yang memenuhi dua invariant:

1. setiap cluster terhubung dan berukuran paling banyak $B$;

2. untuk setiap dua cluster bertetangga $U,V$,

   $$ |U|+|V|>B. $$

Cluster bertetangga berarti ada sisi pohon yang menghubungkan keduanya.

Invariant kedua mengatakan bahwa tidak ada dua cluster bertetangga yang masih bisa digabung tanpa melampaui batas ukuran.

5.1 Mengapa cluster harus terhubung?

Untuk setiap cluster $C$, ada tepat satu simpul di dalamnya yang paling dekat dengan akar. Sebut simpul itu

$$ h(C). $$

Karena $C$ terhubung, seluruh jalur dari $h(C)$ ke setiap $v\in C$ berada di dalam $C$.

Kita dapat menyimpan prefix himpunan

$$ F(v)=P(h(C),v). $$

Prefix ini akan menjadi unit laporan yang berguna ketika query naik keluar dari sebuah cluster.

5.2 Membentuk partisi awal

Mulai dengan setiap simpul sebagai satu cluster.

Proses simpul dari bawah ke atas. Ketika cluster yang berkepala di $v$ sudah selesai diproses, gabungkan ke cluster orang tuanya jika jumlah ukurannya tidak melebihi $B$.

Karena pada pohon awal berlaku $p(v)<v$, urutan label menurun dapat digunakan untuk proses ini.

Jika suatu sisi antarkluster tidak digabung ketika diperiksa, jumlah ukuran kedua cluster saat itu lebih dari $B$. Cluster di sisi atas selanjutnya hanya dapat membesar. Cluster di sisi bawah sudah selesai diproses, kecuali apabila kelak bergabung dengan sisi atas.

Jadi setiap sisi yang tersisa pada akhir proses memenuhi invariant:

$$ |U|+|V|>B. $$

Selama menyusun partisi, cukup ubah daftar anggota. Bangun prefix himpunan setelah partisi akhir tersedia; membangun prefix pada setiap penggabungan sementara akan membayar hal yang tidak diperlukan.

5.3 Membangun prefix di dalam cluster

Untuk kepala cluster:

$$ F(h(C))=\{h(C)\}. $$

Untuk simpul lainnya:

$$ F(v)=F(p(v))\mathbin{\dot\cup}\{v\}. $$

Gabungan tersebut legal karena $v\notin P(h(C),p(v))$.

Jika kedalaman $v$ relatif terhadap $h(C)$ adalah $d_C(v)$, biaya pembentukan $F(v)$, untuk $v\ne h(C)$, adalah

$$ d_C(v)+1. $$

Untuk cluster berukuran $s$, total biaya pembangunan ulangnya adalah

$$ \sum_{v\ne h(C)}\bigl(d_C(v)+1\bigr). $$

Jumlah kedalaman maksimum pada pohon berakar berukuran $s$ terjadi pada rantai:

$$ \sum_v d_C(v)\le \frac{s(s-1)}2. $$

Maka biaya pembangunan ulang memenuhi

$$ \operatorname{rebuild}(C) \le \frac{s(s-1)}2+(s-1) = \frac{s(s+1)}2-1. $$

Untuk $s\le 64$:

$$ \operatorname{rebuild}(C)\le \frac{64\cdot65}{2}-1 =2079. $$

Jika ukuran cluster awal adalah $s_1,\ldots,s_k$, biaya preprocessing prefix memenuhi:

$$ C_{\mathrm{init},B} \le \sum_{i=1}^k\left(\frac{s_i(s_i+1)}2-1\right) \le \frac{n(B+1)}2. $$

Untuk penilaian $C_2$, biaya ini tidak masuk ke maksimum biaya operasi.

5.4 Menjawab query

Misalkan

$$ w=\operatorname{LCA}(x,y), $$

dan $C_w$ adalah cluster yang memuat $w$.

Selama $x$ belum berada di $C_w$:

1. laporkan $F(x)$;
2. ganti $x$ dengan $p(h(C_x))$.

Lakukan hal yang sama untuk $y$.

Setelah kedua ujung berada di $C_w$, laporkan singleton pada sisa jalur:

• dari $x$ ke $w$, tanpa $w$;
• dari $y$ ke $w$, tanpa $w$;
• lalu $\{w\}$ sekali.

Pseudocode:

ask(x, y):
    w = lca(x, y)
    z = cluster(w)
    while cluster(x) != z:
        report(F[x])
        x = parent(head(cluster(x)))
    while cluster(y) != z:
        report(F[y])
        y = parent(head(cluster(y)))
    while x != w:
        report(singleton[x])
        x = parent(x)
    while y != w:
        report(singleton[y])
        y = parent(y)
    report(singleton[w])

5.5 Pembuktian correctness query

Saat $x$ berada di cluster yang tidak memuat $w$, jalur $x\to w$ keluar dari cluster tersebut melalui sisi

$$ \bigl(h(C_x),p(h(C_x))\bigr). $$

Bagian jalur sebelum keluar tepat sama dengan $F(x)$. Setelah melaporkannya dan memindahkan $x$ ke $p(h(C_x))$, kita sudah menghapus satu bagian jalur tanpa kehilangan atau menduplikasi simpul.

Cluster yang berbeda saling lepas. Dua sisi query hanya bertemu pada bagian yang memuat LCA. Bagian terakhir dilaporkan sebagai singleton, dengan $w$ tepat sekali.

Karena itu, seluruh laporan membentuk partisi tepat dari $P(x,y)$.

Sebagai contoh, ambil rantai:

$$ 1\to2\to3\to4\to5\to6\to7\to8\to9, $$

dengan $B=4$ dan sebuah partisi legal:

$$ C_1=\{1,2,3\},\qquad C_2=\{4,5,6\},\qquad C_3=\{7,8,9\}. $$

Untuk query $(2,8)$, laporan yang dipakai adalah:

$$ \{7,8\},\quad \{4,5,6\},\quad \{3\},\quad \{2\}. $$

Prefix pada cluster terakhir tidak memasukkan simpul $9$. Jadi kita tidak mengharuskan query memakai seluruh isi setiap cluster yang dilewati.

5.6 Batas banyaknya cluster pada jalur

Kontraksikan setiap cluster menjadi satu simpul. Karena setiap cluster terhubung, graf hasil kontraksi tetap sebuah pohon.

Misalkan sebuah jalur melewati $k$ cluster dengan ukuran

$$ s_1,s_2,\ldots,s_k. $$

Invariant memberikan

$$ s_i+s_{i+1}\ge B+1. $$

Pasangkan cluster secara tidak tumpang tindih:

$$ (s_1,s_2),(s_3,s_4),\ldots. $$

Karena semua cluster tersebut saling lepas:

$$ \left\lfloor\frac{k}{2}\right\rfloor(B+1) \le \sum_{i=1}^k s_i \le n. $$

Akibatnya,

$$ k\le 2\left\lfloor\frac{n}{B+1}\right\rfloor+1. $$

Query melaporkan satu prefix untuk setiap cluster selain cluster LCA, dan paling banyak $B$ singleton di cluster LCA. Jadi:

$$ \operatorname{cost}_{\mathrm{ask}} \le (k-1)+B \le 2\left\lfloor\frac{n}{B+1}\right\rfloor+B. $$

Untuk $n\le 10^5$ dan $B=64$:

$$ \operatorname{cost}_{\mathrm{ask}} \le 2\left\lfloor\frac{100000}{65}\right\rfloor+64 =3140. $$

Query tidak membuat himpunan baru, sehingga ini adalah seluruh biayanya.

5.7 Apa yang berubah saat satu sisi dipindahkan?

Anggap orang tua $x$ berubah dari $a$ menjadi $y$.

Jika sisi $(a,x)$ berada di antara dua cluster, tidak ada cluster yang perlu dipecah.

Jika sisi tersebut berada di dalam satu cluster $C$, hapus sisi itu dari subpohon yang diinduksi $C$. Karena $C$ terhubung, kita memperoleh tepat dua bagian terhubung:

• $C_{\mathrm{up}}$, yang memuat kepala lama;
• $C_{\mathrm{down}}$, yang memuat $x$.

Beberapa bagian bisa dipandang kosong pada kasus ketika pemindahan tidak memotong bagian internal cluster.

Ukuran setiap bagian tidak melebihi $B$. Masalahnya adalah invariant ukuran tetangga: setelah sebuah cluster mengecil, ia mungkin dapat digabung dengan tetangganya.

5.8 Memulihkan invariant dengan penggabungan greedy

Untuk setiap bagian yang berubah, selama ada cluster tetangga $D$ dengan

$$ |C|+|D|\le B, $$

gabungkan keduanya sebagai satu cluster.

Yang digabung di sini adalah keanggotaan cluster dalam struktur data. Kita belum memanggil $\operatorname{merge}$ untuk membangun prefix himpunannya.

Setelah partisi stabil, barulah prefix untuk cluster akhir yang berubah dibangun ulang.

5.9 Mengapa greedy ini aman?

Ada dua klaim terpisah.

Klaim pertama: penggabungan mempertahankan keterhubungan dan batas ukuran.

Kedua cluster bertetangga, sehingga gabungannya terhubung. Syarat penggabungan memastikan ukuran hasilnya paling banyak $B$.

Klaim kedua: pelanggaran invariant hanya dapat berada di sekitar bagian yang berubah.

Sebelum modifikasi, dua cluster lama yang bertetangga sudah mempunyai jumlah ukuran lebih besar dari $B$.

Misalkan cluster berubah $C$ menyerap cluster lama $D$. Untuk tetangga lama $E$ dari $D$:

$$ |D|+|E|>B \quad\Longrightarrow\quad |C\cup D|+|E|>B. $$

Jadi pembesaran cluster tidak menciptakan pelanggaran baru pada sisi yang sebelumnya sudah aman. Pelanggaran yang masih mungkin hanya yang melibatkan bagian yang semula mengecil atau hubungan baru akibat pemindahan.

Proses berhenti karena setiap penggabungan mengurangi jumlah cluster.

5.10 Mengapa hanya dua cluster akhir yang perlu dibangun ulang?

Tandai kedua bagian dari cluster yang terpotong.

Setiap penggabungan untuk memperbaiki partisi selalu melibatkan cluster yang memuat setidaknya salah satu tanda tersebut. Cluster lama yang terserap tidak perlu dibangun ulang sebagai objek terpisah karena ia sudah tidak menjadi cluster aktif.

Pada akhir proses, paling banyak ada dua cluster aktif yang mengandung tanda:

• satu cluster untuk bagian atas;
• satu cluster untuk bagian bawah;
• atau satu cluster saja jika keduanya akhirnya bergabung.

Cluster aktif lain mempunyai struktur internal yang sama seperti sebelumnya. Mengganti orang tua kepala sebuah cluster tidak mengubah prefix di dalam cluster tersebut.

Jadi cukup membangun ulang paling banyak dua cluster.

5.11 Batas biaya modifikasi

Biaya modifikasi hanya berasal dari pembangunan ulang prefix:

$$ \operatorname{cost}_{\mathrm{modify}} \le 2\cdot2079 =4158. $$

Mengubah pointer, memecah daftar anggota, memperbarui struktur pencarian tetangga, dan memperbaiki partisi tidak menambah biaya soal.

Dengan hasil query sebelumnya:

$$ C_2 \le \max(3140,4158) =4158<5000. $$

Ini adalah jaminan worst-case untuk subtask $3$ dan $5$.

5.12 Mengapa memilih $B=64$?

Untuk parameter umum $B$:

$$ \operatorname{cost}_{\mathrm{modify}} \le B(B+1)-2, $$

sedangkan

$$ \operatorname{cost}_{\mathrm{ask}} \le 2\left\lfloor\frac{n}{B+1}\right\rfloor+B. $$

Parameter $B$ menyeimbangkan biaya rebuild yang kuadratik dengan banyaknya cluster pada jalur yang berbanding terbalik terhadap $B$.

$B=64$ bukan satu-satunya pilihan yang mungkin. Ia memberikan ruang aman terhadap batas $5000$ pada kedua jenis operasi.

5.13 Mencari cluster tetangga yang bisa digabung

Kita tidak boleh memindai seluruh anak pohon setiap kali sebuah cluster berubah.

Untuk setiap simpul asli $u$, simpan struktur terurut:

$$ \mathcal C(u) = \{(|D|,D):p(h(D))=u\}. $$

Artinya, $\mathcal C(u)$ berisi cluster anak yang menempel langsung pada $u$.

Untuk setiap cluster $C$, simpan:

$$ \mathcal M(C) = \{(\min\operatorname{size}(\mathcal C(u)),u): u\in C,\ \mathcal C(u)\ne\varnothing\}. $$

Dengan demikian:

• cluster orang tua dapat ditemukan melalui $p(h(C))$;
• cluster anak berukuran minimum dapat ditemukan melalui elemen minimum $\mathcal M(C)$.

Jika anak terkecil pun tidak muat, tidak ada anak lain yang muat.

Struktur ini diimplementasikan menggunakan ordered set. Dalam kode, keduanya bersesuaian dengan $\texttt{cs}$ dan $\texttt{mn}$.

5.14 Peran Link-Cut Tree pada Algoritma B

Link-Cut Tree hanya digunakan untuk mempertahankan struktur pohon dan mencari LCA. Tidak ada himpunan jalur besar yang disimpan sebagai agregat LCT.

Karena akar tetap $1$, kita dapat menggunakan LCT tanpa operasi pembalikan jalur:

$$ \operatorname{access}(x); \qquad w=\operatorname{access}(y). $$

Nilai terakhir yang dicapai oleh access kedua memberikan LCA.

Ini memisahkan dua urusan:

• LCT mengurus hubungan pohon;
• cluster mengurus himpunan yang akan dilaporkan.

5.15 Kompleksitas Algoritma B

Biaya soal sudah mempunyai batas eksplisit:

$$ \begin{aligned} \operatorname{ask}&\le 2\left\lfloor\frac{n}{B+1}\right\rfloor+B,\\ \operatorname{modify}&\le B(B+1)-2. \end{aligned} $$

Untuk waktu CPU di luar pustaka:

• LCA dan perubahan sisi menggunakan $O(\log n)$ amortized;
• query menggunakan tambahan $O(n/B+B)$ langkah;
• memecah cluster dan rebuild prefix mengunjungi $O(B)$ simpul;
• perbaikan partisi memindahkan daftar anggota dan memperbarui ordered set.

Batas konservatif untuk bagian terakhir adalah $O(B^2\log n)$ per modifikasi: setiap penggabungan menambah ukuran cluster, ukuran akhirnya paling banyak $B$, dan setiap perpindahan anggota memerlukan operasi ordered set.

Batas ini sengaja konservatif; banyak perpindahan hanya memproses cluster kecil yang baru diserap. Kita tidak memerlukan klaim bahwa seluruh modifikasi hanya $O(\log n)$.

Penyusunan partisi awal dengan daftar anggota sederhana mempunyai batas konservatif $O(nB)$ untuk perpindahan anggota, diikuti pembangunan struktur terurut dalam $O(n\log n)$ dan pembangunan prefix dengan $O(n)$ pemanggilan pustaka.

Untuk memori, jumlah anggota aktif adalah $n$ dan jumlah ID cluster yang pernah dibuat adalah $O(n+q)$. Dengan mempertimbangkan kapasitas vektor cluster yang sudah tidak aktif, batas parametrik yang aman untuk implementasi adalah

$$ O((n+q)B). $$

Karena $B=64$ tetap, ini adalah $O(n+q)$ terhadap parameter masukan. Handle prefix dan singleton membutuhkan $O(n)$ ruang.

6. Mengapa Algoritma B belum ideal untuk penilaian biaya total?

Batas satu operasi yang kecil tidak otomatis memberikan biaya total di bawah ambang subtask $4$.

Jika terdapat banyak modifikasi, pembukuan kasar memberikan

$$ C_1 \le C_{\mathrm{init}}

4158\,q_{\mathrm{modify}}

3140\,q_{\mathrm{ask}}. $$

Untuk $q=10^5$, batas ini masih dapat melampaui $150$ juta.

Masalahnya terutama muncul ketika kita berkali-kali membangun prefix yang mahal, padahal query berikutnya hanya memerlukan sebagian kecil darinya.

Untuk biaya total, kita ingin:

1. mempertahankan himpunan lama selama masih dapat digunakan;
2. tidak membangun himpunan besar hanya karena auxiliary tree berubah;
3. membentuk agregat kecil dengan segera, tetapi menunda agregat yang lebih mahal;
4. memanfaatkan struktur rantai panjang secara khusus.

Inilah tujuan Algoritma A.

7. Subtask 2: pohon berbentuk kumpulan lengan

Syarat khususnya adalah:

$$ \forall v\ne1,\qquad \deg^+(v)\le1. $$

Maka setiap anak akar memulai sebuah rantai. Pohon merupakan beberapa lengan yang bertemu pada akar.

Contohnya:

$$ 1\to a_1\to a_2\to\cdots,\qquad 1\to b_1\to b_2\to\cdots. $$

Query memiliki bentuk sederhana:

• dua simpul pada lengan yang sama: satu interval rantai;
• dua simpul pada lengan berbeda: dua prefix lengan dan singleton akar;
• salah satu ujung di akar: satu prefix lengan dan akar.

Modifikasi pada pohon legal dapat dipahami sebagai:

1. memotong suffix suatu lengan;
2. menempelkannya ke akar atau ke ujung lengan lain.

Jadi struktur dasarnya adalah sekumpulan sequence yang mendukung split dan concatenate.

7.1 Sequence dalam balanced tree

Simpan urutan simpul pada sebuah lengan dalam balanced binary search tree berdasarkan posisi implisit.

Operasi yang diperlukan:

$$ \operatorname{split}(T,k) $$

untuk memisahkan $k$ elemen pertama, dan

$$ \operatorname{concat}(A,B) $$

untuk menyambungkan dua sequence.

AVL menyediakan tinggi $O(\log n)$ dan dapat mendukung kedua operasi tersebut.

Namun, agregat himpunannya tidak diperbarui secara eager pada setiap perubahan. Kita akan menggunakan mekanisme cache dan materialisasi dari bagian berikut.

7.2 Hubungan dengan solusi umum

Algoritma A akan mengontraksikan setiap rantai tanpa percabangan menjadi satu simpul makro.

Pada subtask $2$, pohon makro tersebut adalah:

• satu simpul jika pohon asli merupakan satu rantai; atau
• sebuah bintang dengan pusat pada rantai yang memuat akar.

Jadi seluruh kesulitan rantai panjang ditangani oleh AVL tingkat pertama. Tidak diperlukan banyak bagian preferred path pada tingkat makro.

Correctness subtask $2$ mengikuti pembuktian umum Algoritma A. Status batas $C_1$ untuk kebijakan materialisasi implementasi tetap seperti yang dijelaskan pada awal tulisan.

8. Algoritma A: kontraksikan semua rantai tanpa percabangan

Untuk simpul asli $v$, tulis

$$ d(v)=\#\{\text{anak dari }v\}. $$

Sebuah rantai normal dimulai pada:

• akar $1$; atau
• simpul yang orang tuanya mempunyai jumlah anak bukan $1$.

Dari kepala tersebut, ikuti anak tunggal selama simpul sekarang mempunyai tepat satu anak.

Rantai berhenti pada simpul dengan:

$$ d(v)=0 \quad\text{atau}\quad d(v)\ge2. $$

Untuk sebuah rantai $C$, definisikan:

$$ h(C)=\text{kepala rantai},\qquad t(C)=\text{ujung bawah rantai}. $$

8.1 Lemma partisi

Setiap simpul asli termasuk dalam tepat satu rantai normal.

Bukti. Naik dari sebuah simpul selama orang tuanya mempunyai tepat satu anak. Proses berhenti pada akar atau pada anak suatu simpul bercabang. Titik berhenti ini unik dan merupakan kepala rantainya. Mengikuti anak tunggal dari kepala tersebut menghasilkan rantai yang unik. $\square$

8.2 Pohon makro

Kontraksikan setiap rantai menjadi satu simpul. Hubungkan kepala rantai $h$ ke pemilik simpul $p(h)$.

Setiap simpul makro mewakili satu himpunan simpul asli, dengan bobot

$$ w(C)=|C|. $$

Setiap simpul makro mempunyai:

• $0$ anak jika ujung rantainya adalah daun;
• setidaknya $2$ anak jika ujung rantainya bercabang.

Tidak ada simpul makro dengan tepat satu anak.

Ini menghilangkan rantai makro yang muncul hanya karena banyak simpul berderajat keluar satu.

Tetapi ini tidak menjamin tinggi $O(\log n)$. Pohon berbentuk sisir tetap dapat mempunyai jalur makro panjang. Karena itu, kita masih memerlukan struktur preferred path pada tingkat makro.

8.3 Dua tingkat struktur data

Kita menggunakan:

1. AVL tingkat $0$: sequence simpul asli pada setiap rantai normal;
2. AVL tingkat $1$: sequence simpul makro pada setiap preferred path.

Nilai sebuah simpul pada tingkat $0$ adalah singleton.

Nilai sebuah simpul pada tingkat $1$ adalah seluruh rantai asli yang diwakilinya.

Perhatikan perbedaan:

$$ \operatorname{size}(u) =\text{jumlah simpul AVL}, $$

sedangkan

$$ \operatorname{weight}(u) =\text{jumlah simpul asli yang diwakili}. $$

Pada tingkat $0$, keduanya sama. Pada tingkat $1$, keduanya bisa sangat berbeda.

Semua batas materialisasi dan biaya penggabungan harus memakai $\operatorname{weight}$.

9. Kepemilikan implisit: menghindari pembaruan massal

Saat dua rantai digabung, kita tidak ingin memperbarui sebuah array pemilik untuk seluruh simpul di rantai yang panjang.

Sebagai gantinya:

$$ \operatorname{owner}(v) = \operatorname{first}\bigl( \operatorname{rootAVL}_0(v) \bigr). $$

Kita naik melalui pointer orang tua AVL tingkat $0$, lalu membaca elemen pertama sequence tersebut. Itulah kepala rantai yang memuat $v$.

Operasi ini membutuhkan $O(\log n)$ waktu dan tidak melakukan penggabungan himpunan.

Prinsip yang sama dipakai untuk orang tua virtual preferred path.

Jika elemen pertama suatu auxiliary tree makro adalah kepala rantai $h$, orang tua virtualnya adalah:

$$ \operatorname{owner}(p(h)). $$

Nilai ini dihitung dari hubungan pohon asli saat dibutuhkan.

Akibatnya, ketika suatu rantai pecah atau bergabung, seluruh anak virtual yang menempel pada simpul di dalamnya langsung memperoleh pemilik yang benar tanpa pembaruan massal.

10. AVL digunakan untuk struktur, bukan untuk memaksa merge

Kita memerlukan operasi standar:

$$ \operatorname{join}(L,x,R), \quad \operatorname{split}(T,k), \quad \operatorname{concat}(L,R). $$

Semua berdasarkan urutan implisit sequence.

Dengan implementasi AVL join/split yang benar, setiap operasi struktural tersebut membutuhkan $O(\log n)$ waktu.

10.1 Metadata suatu subtree

Untuk setiap simpul AVL $u$, kita simpan:

Semua metadata selain handle himpunan dapat dihitung dari anak-anaknya dalam $O(1)$.

10.2 Cache lokal ketika rotasi

Rotasi mengubah bentuk binary tree, tetapi tidak mengubah himpunan elemen pada keseluruhan subtree yang dirotasi.

Jika sebelum rotasi subtree berakar di $u$ mempunyai agregat sah $G$, sesudah rotasi agregat $G$ dapat dipindahkan ke akar baru subtree tersebut.

Kita tidak perlu memanggil $\operatorname{merge}$ untuk mempertahankan agregat keseluruhan.

Agregat pada subtree yang benar-benar berubah isinya ditandai belum tersedia.

10.3 Mengapa memilih struktur deterministik?

AVL menyediakan tinggi $O(\log n)$ secara deterministik. Tidak dibutuhkan prioritas acak untuk menjamin bentuk tree.

Hal ini tidak mengubah status analisis biaya $C_1$: tinggi balanced tree yang kecil belum otomatis memberikan biaya penggabungan kecil. Ia hanya membatasi pekerjaan struktural.

11. Access pada tingkat makro

Preferred path dipertahankan seperti pada dynamic tree biasa, tetapi setiap auxiliary tree direpresentasikan dengan AVL sequence.

Untuk melakukan $\operatorname{access}(x)$:

1. temukan akar auxiliary tree yang memuat $x$;
2. pecah sequence tepat setelah $x$;
3. suffix lama menjadi preferred path terpisah;
4. sambungkan prefix dengan bagian yang sudah dikumpulkan dari bawah;
5. lanjutkan ke orang tua virtual kepala auxiliary tree lama.

Pseudocode:

access(x):
    cur = empty sequence
    u = x
    while u != 0:
        r = auxiliary_root(u)
        v = owner(parent(first(r)))
        (a, b) = split(r, rank(u))
        cur = concat(a, cur)
        remember u and b
        u = v
    return cur and the remembered information

Tidak ada merge himpunan yang wajib dilakukan selama access.

11.1 Informasi dari dua access

Setelah:

$$ \operatorname{access}(a), \qquad \operatorname{access}(b), $$

kita dapat memperoleh:

• LCA makro $w$;
• preferred path baru yang berakhir pada $b$;
• suffix dari sisi $a$ yang terlepas pada langkah terakhir.

Sisi terakhir inilah yang dipakai implementasi untuk melaporkan cabang menuju $a$ tanpa menjalankan access tambahan.

12. Mempertahankan rantai normal saat modifikasi

Satu perubahan orang tua hanya mengubah jumlah anak pada dua simpul:

$$ a=p_{\mathrm{old}}(x), \qquad y=p_{\mathrm{new}}(x). $$

Maka hanya ada sejumlah konstan batas rantai yang perlu diubah.

Kita membutuhkan dua operasi dasar.

12.1 Memotong rantai sebelum $x$

Jika $x$ sudah menjadi kepala rantai, tidak ada yang perlu dilakukan.

Jika tidak:

1. cari kepala rantai $h=\operatorname{owner}(x)$;
2. lakukan access makro pada $h$, agar preferred suffix di bawahnya terlepas;
3. pecah AVL tingkat $0$ tepat sebelum $x$;
4. prefix tetap menjadi rantai berkepala $h$;
5. suffix menjadi rantai baru berkepala $x$;
6. perbarui bobot makro $h$ dan aktifkan simpul makro $x$.

Jumlah simpul asli yang dipindahkan secara eksplisit adalah nol: pemecahan dilakukan melalui pointer AVL.

12.2 Menggabungkan rantai anak ke rantai orang tua

Operasi ini dilakukan ketika orang tua kepala rantai $x$ mempunyai tepat satu anak, yaitu $x$.

Misalkan

$$ h=\operatorname{owner}(p(x)). $$

Lakukan:

1. access makro pada $x$;
2. pisahkan simpul makro $x$ dari ujung preferred path;

3. sambungkan sequence asli:

   $$ C_h\leftarrow C_h\Vert C_x; $$

4. nonaktifkan simpul makro $x$;

5. perbarui bobot simpul makro $h$.

Simbol $\Vert$ menyatakan concatenation sequence, bukan operasi merge himpunan.

12.3 Urutan lengkap modifikasi

Untuk $\operatorname{modify}(x,y)$:

1. Jika $p(x)=y$, selesai.
2. Perbarui timestamp sisi yang masuk ke $x$.
3. Jika $x$ berada di tengah rantai, potong rantai sebelum $x$.
4. Lepaskan hubungan makro dari $x$ menuju orang tua lamanya.
5. Kurangi jumlah anak orang tua lama.
6. Jika orang tua lama sekarang mempunyai tepat satu anak, gabungkan rantainya dengan rantai anak yang tersisa.
7. Jika $y$ sebelumnya mempunyai tepat satu anak, potong rantai sebelum anak tersebut: setelah penempelan, $y$ akan menjadi titik percabangan.
8. Hubungkan $x$ sebagai anak $y$.
9. Jika $y$ sebelumnya merupakan daun, gabungkan rantai yang berakhir di $y$ dengan rantai yang dimulai di $x$.

Ada paling banyak dua pemotongan rantai dan dua penggabungan rantai.

12.4 Mengetahui anak tunggal dalam $O(1)$

Simpan:

$$ d(u)=\#\text{anak }u, $$

dan

$$ \chi(u)=\bigoplus_{v:\,p(v)=u}v. $$

Jika $d(u)=1$, maka $\chi(u)$ adalah anak tunggal tersebut.

Penambahan atau penghapusan anak cukup memperbarui hitungan dan satu XOR.

12.5 Pembuktian invariant normalisasi

Sebelum modifikasi, semua rantai normal.

Pemotongan sisi hanya dapat menyebabkan:

• $x$ harus menjadi kepala rantai baru;
• orang tua lama kehilangan status bercabang dan menjadi simpul beranak satu.

Penambahan sisi hanya dapat menyebabkan:

• $y$ berubah dari beranak satu menjadi bercabang;
• $y$ berubah dari daun menjadi beranak satu.

Keempat kemungkinan tersebut tepat ditangani oleh langkah-langkah di atas. Jumlah anak simpul lain tidak berubah.

Setelah operasi selesai, seluruh rantai kembali maksimal dan setiap simpul makro mempunyai $0$ atau setidaknya $2$ anak. Partisi simpul tetap tepat.

13. Menerjemahkan query asli menjadi interval pada dua tingkat

Misalkan:

$$ A=\operatorname{owner}(x), \qquad D=\operatorname{owner}(y). $$

13.1 Kedua ujung berada pada rantai yang sama

Jika $A=D$, jalur asli adalah interval pada AVL tingkat $0$:

$$ \bigl[ \min(\operatorname{rank}(x),\operatorname{rank}(y)), \max(\operatorname{rank}(x),\operatorname{rank}(y)) \bigr]. $$

Tidak diperlukan access makro.

13.2 Kedua ujung berada pada rantai berbeda

Misalkan $W$ adalah LCA dari $A$ dan $D$ pada pohon makro.

Bagilah jawaban menjadi:

1. rantai makro interior di cabang $A\to W$;
2. rantai makro interior di cabang $D\to W$;
3. bagian rantai yang memuat $x$;
4. bagian rantai yang memuat $y$;
5. bila diperlukan, satu simpul asli di dalam rantai $W$.

Bagian interior tidak memasukkan $A,D,W$.

Untuk bagian yang memuat $x$:

$$ \begin{cases} P(x,t(C_A)),&W=A,\\ P(h(C_A),x),&W\ne A. \end{cases} $$

Untuk bagian yang memuat $y$:

$$ \begin{cases} P(y,t(C_D)),&W=D,\\ P(h(C_D),y),&W\ne D. \end{cases} $$

Jika $W\notin\{A,D\}$, tambahkan:

$$ \{t(C_W)\}. $$

13.3 Mengapa hanya ujung bawah rantai LCA?

Jika dua rantai anak berbeda keluar dari rantai $W$, keduanya keluar melalui titik percabangan yang sama, yaitu $t(C_W)$.

Jalur di antara kedua cabang hanya melewati simpul tersebut. Melaporkan seluruh $C_W$ akan menambahkan simpul-simpul di atas LCA asli yang tidak termasuk jawaban.

Ini merupakan salah satu detail correctness yang paling mudah terlewat.

13.4 Pembuktian partisi jawaban

Rantai normal saling lepas.

Setiap rantai interior dilewati seluruhnya. Pada rantai ujung, jalur hanya memakai prefix atau suffix yang disebutkan. Pada rantai LCA yang bukan rantai ujung, jalur hanya memakai titik percabangannya.

Semua bagian tersebut saling lepas dan gabungannya tepat sama dengan jalur asli. Karena itu, setelah setiap interval dilaporkan dengan benar, query keseluruhan juga benar.

Contoh kecil yang memperlihatkan peran rantai LCA:

$$ 1\to2\to3,\qquad 3\to4\to6,\qquad 3\to5\to7. $$

Rantai normalnya adalah:

$$ C_1=(1,2,3),\qquad C_4=(4,6),\qquad C_5=(5,7). $$

Untuk query $(6,7)$, LCA makro adalah $C_1$, tetapi jawabannya:

$$ \{4,6\}\mathbin{\dot\cup}\{3\} \mathbin{\dot\cup}\{5,7\}. $$

Simpul $1$ dan $2$ tidak dilaporkan.

Untuk query $(2,6)$, salah satu ujung justru berada pada rantai LCA. Jawabannya:

$$ \{2,3\}\mathbin{\dot\cup}\{4,6\}. $$

Bagian pertama adalah suffix rantai $C_1$ yang dimulai pada $2$.

13.5 Shortcut ketika kedua rantai berada pada auxiliary tree yang sama

Jika $A$ dan $D$ sudah berada pada satu preferred path, kita tidak perlu mengubah preferred path dengan dua access.

Urutkan keduanya menurut rank. Laporkan:

• interval makro yang terletak ketat di antara keduanya;
• suffix rantai ujung atas;
• prefix rantai ujung bawah.

Shortcut ini mempertahankan lebih banyak cache yang sudah tersedia dan mengurangi pembentukan representasi baru, terutama untuk query berulang pada backbone panjang.

14. Cache interval yang tetap benar setelah pohon berubah

Himpunan yang sudah dibuat tidak pernah berubah. Yang bisa berubah adalah apakah himpunan tersebut masih mewakili suatu interval jalur pada pohon sekarang.

Kita ingin menggunakan kembali himpunan lama untuk interval berujung:

$$ (s,t), $$

dengan $s$ leluhur $t$.

Karena pohon mempunyai jalur unik, pasangan ujung ini cukup untuk mengidentifikasi interval pada suatu keadaan pohon.

Kunci cache berorientasi dari atas ke bawah. Kita tidak mengurutkan label $s,t$ berdasarkan besar-kecilnya.

14.1 Timestamp sisi masuk

Simpan:

$$ m(v)=\text{waktu terakhir orang tua }v\text{ diubah}. $$

Timestamp bertambah hanya ketika terjadi perubahan orang tua yang sesungguhnya.

Untuk interval $Q=P(s,t)$, definisikan:

$$ \mu(Q)=\max_{v\in Q}m(v), $$

dan

$$ \nu(Q)=\max_{v\in Q\setminus\{s\}}m(v). $$

Maksimum himpunan kosong didefinisikan sebagai $0$.

14.2 Kriteria validitas

Misalkan cache untuk $(s,t)$ dibuat pada waktu $\tau$.

Kita boleh menggunakannya bila

$$ \nu(P(s,t))\le\tau. $$

Bukti. Setiap sisi internal interval sekarang berbentuk $(p(v),v)$ untuk $v\ne s$. Syarat di atas memastikan bahwa orang tua semua simpul tersebut tidak berubah setelah waktu $\tau$.

Jadi seluruh sisi internal interval sekarang juga ada pada waktu $\tau$. Karena jalur di pohon unik, interval sekarang mempunyai himpunan simpul yang sama dengan interval ketika cache dibuat. $\square$

Kriteria ini cukup untuk keamanan. Kita tidak perlu berusaha mendeteksi semua cache yang kebetulan menjadi valid kembali setelah suatu urutan perubahan.

14.3 Mengapa timestamp simpul pertama dikecualikan?

Sisi masuk ke $s$ berada di luar interval.

Jika seluruh subtree yang berakar pada $s$ dipindahkan, jalur internal dari $s$ ke $t$ bisa tetap identik. Memasukkan $m(s)$ akan membatalkan cache yang masih benar.

Mengecualikannya meningkatkan penggunaan ulang tanpa melemahkan correctness.

14.4 Menggabungkan metadata timestamp

Jika sequence adalah:

$$ Q=L\Vert V\Vert R, $$

maka:

$$ \mu(Q)=\max(\mu(L),\mu(V),\mu(R)). $$

Jika $L$ tidak kosong:

$$ \nu(Q)=\max(\nu(L),\mu(V),\mu(R)). $$

Jika $L$ kosong:

$$ \nu(Q)=\max(\nu(V),\mu(R)). $$

Rumus yang sama berlaku ketika $V$ adalah singleton ataupun sebuah rantai berbobot.

14.5 Cache lokal dan cache global

Ada dua bentuk cache:

• cache lokal pada simpul AVL, untuk himpunan subtree AVL saat ini;
• cache global berdasarkan pasangan ujung interval.

Rotasi boleh memindahkan cache keseluruhan karena himpunannya tetap sama. Split, join, dan pembaruan timestamp membatalkan cache lokal pada bagian yang berubah.

Cache global baru digunakan setelah pemeriksaan timestamp. Kedua mekanisme ini saling melengkapi.

15. Materialisasi himpunan secara selektif

Ketika perlu melaporkan sebuah subtree AVL, kita mencoba langkah berikut:

1. pakai cache lokal jika tersedia;
2. pakai cache global jika timestamp-nya valid;
3. gunakan himpunan berdasarkan interval label jika memungkinkan;
4. jika bobotnya kecil, buat agregatnya;
5. jika terlalu besar, pecah menjadi beberapa bagian dan laporkan bagian-bagian tersebut.

Dalam implementasi:

$$ \beta=384 $$

adalah batas materialisasi langsung tingkat $0$, dan

$$ \gamma=96 $$

adalah batas materialisasi langsung tingkat $1$.

Batas ini diterapkan pada jumlah simpul asli, bukan pada jumlah simpul makro.

15.1 Mengapa menolak membentuk agregat besar?

Sebuah subtree besar bisa baru muncul akibat split atau concatenation. Membentuk agregatnya sekarang belum tentu bermanfaat, karena subtree tersebut mungkin tidak akan diminta lagi.

Melaporkannya sebagai beberapa himpunan lebih kecil menghindari pembayaran besar yang belum tentu dapat dipakai ulang.

15.2 Urutan dua penggabungan

Misalkan bagian kiri berukuran $a$, nilai sendiri berukuran $c$, dan bagian kanan berukuran $b$.

Jika bagian kiri digabung lebih dahulu:

$$ (a+c)+(a+b+c). $$

Jika bagian kanan digabung lebih dahulu:

$$ (b+c)+(a+b+c). $$

Selisih keduanya adalah $a-b$. Karena itu, di antara kedua pilihan ini, kita menggabungkan nilai sendiri dengan anak yang lebih kecil terlebih dahulu.

Ini adalah optimasi lokal yang mempunyai bukti langsung. Ia bukan klaim bahwa seluruh kebijakan materialisasi menjadi optimal secara global.

15.3 Simpan juga hasil parsial

Jika sudah membayar untuk membentuk:

$$ L\cup V \quad\text{atau}\quad V\cup R, $$

simpan pula hasil tersebut pada cache pasangan ujung.

Sesudah rotasi atau split berikutnya, interval parsial ini mungkin muncul kembali walaupun interval keseluruhannya tidak.

Validitasnya tetap diperiksa dengan aturan timestamp yang sama.

16. Memanfaatkan himpunan yang merupakan interval label

Label simpul tidak mempunyai hubungan wajib dengan urutan jalur. Namun, kadang himpunan pada suatu bagian jalur kebetulan sama dengan interval label.

Misalkan sebuah himpunan terdiri dari $w$ simpul berbeda, dengan label minimum $a$ dan maksimum $b$. Jika

$$ w=b-a+1, $$

maka himpunan tersebut tepat:

$$ \{a,a+1,\ldots,b\}. $$

Bukti. Semua $w$ label berada pada interval yang mempunyai tepat $w$ nilai mungkin. Karena semuanya berbeda, seluruh nilai harus muncul. $\square$

16.1 Segment tree statis berdasarkan label

Pada awal program, bangun himpunan untuk node-node segment tree pada urutan label:

$$ 1,2,\ldots,n. $$

Himpunan-himpunan ini sah sepanjang program karena keanggotaan berdasarkan label tidak berubah.

Jika bagian query sama dengan satu node segment tree, kita langsung memakai handle-nya.

Jika ia merupakan interval label umum, kita melaporkan canonical cover segment tree, dengan $O(\log n)$ himpunan.

Tidak ada syarat bahwa label harus muncul secara menaik pada jalur. Yang dibutuhkan hanya kesamaan himpunan.

16.2 Biaya preprocessing

Membangun semua himpunan segment tree memerlukan:

$$ O(n\log n) $$

biaya soal, karena pada setiap tingkat, jumlah ukuran seluruh node yang dibentuk adalah $O(n)$.

Jangan menyebut biayanya $O(n)$ hanya karena jumlah node segment tree adalah $O(n)$.

16.3 Himpunan seluruh simpul selain akar

Implementasi juga menyimpan:

$$ U=\{2,3,\ldots,n\}. $$

Jika metadata menunjukkan:

$$ \operatorname{min}=2,\qquad \operatorname{max}=n,\qquad \operatorname{weight}=n-1, $$

maka himpunannya pasti $U$.

Ini adalah kasus khusus reuse himpunan berdasarkan identitas anggotanya.

17. Promosi agregat berdasarkan pemakaian

Ada kasus ketika sebuah interval terlalu besar untuk materialisasi langsung, tetapi diminta berkali-kali.

Melaporkannya sebagai banyak bagian setiap saat juga mahal. Kita ingin membeli agregatnya setelah ada cukup bukti bahwa interval tersebut berguna.

Implementasi melakukan promosi pada interval makro dengan:

$$ \operatorname{weight}\le\Delta,\qquad \Delta=1024. $$

17.1 Memakai bagian yang sudah dilaporkan

Misalkan interval $Q$ baru saja dijawab menggunakan:

$$ Q=A_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}A_k. $$

Semua handle $A_i$ dicatat. Karena laporan tersebut merupakan partisi, penggabungan di antara bagian-bagiannya legal.

Total ukuran:

$$ w=\sum_{i=1}^k|A_i|. $$

Jika $k\le1$, tidak diperlukan promosi.

17.2 Biaya menggabungkan secara seimbang

Gabungkan bagian-bagian tersebut dengan binary tree seimbang berdasarkan banyaknya bagian.

Tingginya paling banyak:

$$ h=\lceil\log_2 k\rceil. $$

Setiap simpul asli berkontribusi pada paling banyak $h$ penggabungan. Maka biaya aktual promosi tidak melebihi:

$$ W=w\lceil\log_2 k\rceil. $$

Ukuran masing-masing $A_i$ tidak harus sama agar batas ini berlaku.

Menggabungkan berurutan dari kiri ke kanan tidak mempunyai batas yang sama; sebuah simpul di bagian awal bisa dibayar ulang terlalu banyak kali.

17.3 Kredit lokal

Untuk interval valid yang belum dipromosikan, tambahkan kredit:

$$ \operatorname{credit}(Q)\mathrel{+}=k-1. $$

Besaran $k-1$ adalah banyak laporan tambahan dibandingkan jika kita sudah mempunyai satu agregat.

Jika interval tidak lagi valid menurut timestamp, kredit lamanya dibuang.

Promosi dipertimbangkan ketika:

$$ \operatorname{credit}(Q)\ge W. $$

Ini menghubungkan pembelian agregat dengan biaya pelaporan yang sudah berulang.

17.4 Anggaran global

Kredit lokal pada interval yang saling bersarang dapat menghitung manfaat yang tumpang tindih. Karena itu, implementasi juga menggunakan anggaran global.

Setiap laporan menambah saldo sebesar $1$.

Setiap penggabungan untuk promosi dengan biaya aktual $c$ mengurangi saldo sebesar $2c$.

Promosi hanya dimulai jika saldo paling sedikit $2W$. Karena biaya aktual promosi paling banyak $W$, saldo tidak menjadi negatif.

Jika:

• $R$ adalah jumlah seluruh laporan;
• $P$ adalah total biaya seluruh promosi,

maka pada setiap saat:

$$ \operatorname{balance}=R-2P\ge0. $$

Jadi:

$$ P\le \frac R2. $$

Ini adalah jaminan matematis untuk biaya promosi.

17.5 Apa yang tidak dibuktikan oleh aturan kredit?

Aturan tersebut tidak membuktikan bahwa semua keputusan cache optimal, atau bahwa total biaya program hanya $1.5R$.

Masih ada biaya pembentukan agregat kecil oleh materialisasi langsung. Biaya tersebut harus dihitung terpisah.

Kredit juga tidak membuktikan bahwa implementasi selalu berada di bawah ambang $150$ juta. Ia memberikan pengendalian yang tepat terhadap satu komponen biaya.

18. Pembuktian correctness Algoritma A

Kita rangkum menjadi beberapa invariant.

Invariant I: partisi rantai

Rantai tingkat $0$ membentuk partisi tepat dari simpul asli, dan setiap rantai adalah rantai normal maksimal.

Invariant ini benar saat inisialisasi dan dipertahankan oleh pemotongan serta penggabungan lokal pada modifikasi.

Invariant II: pohon makro

Setiap simpul makro aktif mewakili satu rantai. Orang tua makronya adalah pemilik orang tua asli kepala rantai tersebut.

Menghitung orang tua virtual melalui kepemilikan implisit mempertahankan invariant ini setelah rantai berubah.

Invariant III: urutan auxiliary tree

Urutan inorder sebuah AVL tingkat $0$ adalah urutan simpul pada satu rantai asli.

Urutan inorder sebuah AVL tingkat $1$ adalah urutan rantai pada satu preferred path makro.

Split, join, concatenate, dan rotasi mempertahankan urutan tersebut.

Invariant IV: setiap handle mewakili himpunan yang benar

Setiap handle baru dibuat dari dua himpunan saling lepas:

• dua bagian yang terpisah dalam suatu sequence; atau
• dua bagian dari partisi laporan saat promosi.

Maka semua pemanggilan merge legal.

Cache lokal hanya dipertahankan ketika himpunan subtree tetap sama. Cache global hanya digunakan setelah pemeriksaan timestamp atau setelah pembuktian identitas melalui interval label.

Invariant V: pelaporan interval adalah partisi

Untuk interval pada AVL, traversal melakukan salah satu hal berikut:

• melaporkan tepat seluruh subtree yang tercakup;
• melaporkan cover segment tree untuk himpunan yang sama;
• memecah interval menjadi bagian kiri, nilai sendiri, dan bagian kanan.

Ketiga bagian terakhir saling lepas. Dengan induksi pada traversal, seluruh laporan merupakan partisi tepat dari interval yang diminta.

Teorema correctness

Untuk setiap urutan operasi legal, Algoritma A melaporkan himpunan simpul pada jalur query secara tepat dan tidak pernah melakukan merge terhadap himpunan yang beririsan.

Bukti. Modifikasi mempertahankan Invariant I–III. Semua pembentukan dan pemakaian handle sah menurut Invariant IV. Query asli dipecah menjadi bagian-bagian saling lepas yang tepat menurut analisis LCA makro. Masing-masing bagian dilaporkan tepat menurut Invariant V. Gabungan seluruhnya adalah jalur query. $\square$

Teorema ini mengenai correctness. Batas biaya total dibahas terpisah.

19. Analisis waktu struktur Algoritma A

19.1 Waktu per operasi AVL

Pada kedua tingkat:

$$ \operatorname{root},\operatorname{rank}, \operatorname{split},\operatorname{join}, \operatorname{concat} $$

memerlukan $O(\log n)$ waktu.

Menghitung owner juga memerlukan $O(\log n)$.

Satu iterasi access melakukan sejumlah konstan operasi tersebut.

19.2 Banyaknya bagian preferred path

Untuk analisis preferred path, gunakan heavy edge konseptual berdasarkan ukuran subtree berbobot:

$$ (u,v)\text{ heavy} \quad\Longleftrightarrow\quad 2\,\operatorname{subtreeWeight}(v)> \operatorname{subtreeWeight}(u). $$

Setiap simpul mempunyai paling banyak satu anak heavy, dan setiap lintasan akar-ke-simpul melewati $O(\log n)$ sisi light.

Pada pohon tetap, gunakan potensial berupa banyaknya heavy edge yang sedang tidak preferred.

Saat access:

• menjadikan heavy edge sebagai preferred menurunkan potensial;
• heavy edge lama dapat kehilangan status preferred ketika dipilih anak light, atau pada ujung access;
• banyaknya kejadian jenis kedua dibatasi oleh banyak sisi light pada jalur, ditambah konstanta.

Ini memberi batas amortized $O(\log n)$ untuk banyaknya pergantian bagian preferred path, selain potensial awal.

Lebih eksplisit, jika sebuah access melewati $h$ heavy edge yang sebelumnya tidak preferred dan $\ell$ light edge, maka heavy edge jenis pertama mengurangi potensial sebanyak $h$. Heavy edge lama yang menjadi tidak preferred dapat dibebankan pada pilihan sisi light atau pelepasan suffix di ujung access. Jadi:

$$ h\le \Phi_{\mathrm{before}}-\Phi_{\mathrm{after}} +\ell+O(1). $$

Karena $\ell=O(\log n)$, jumlah iterasi dapat diamortisasi dengan potensial tersebut.

Cut dan link mengubah ukuran subtree hanya pada jalur leluhur terkait. Untuk sebuah simpul pada jalur itu, jika anak yang menuju lokasi perubahan tetap heavy baik sebelum maupun sesudah perubahan, tidak ada anak lain yang dapat menjadi heavy. Jadi perubahan klasifikasi hanya mungkin pada titik yang sisi jalurnya light sebelum atau sesudah perubahan.

Masing-masing jalur memiliki $O(\log n)$ sisi light, sehingga ada $O(\log n)$ perubahan klasifikasi. Setiap perubahan memengaruhi potensial sebesar konstanta.

Pemecahan rantai membagi bobot satu simpul makro menjadi dua simpul makro bertetangga. Total bobot subtree yang terlihat dari leluhur lama tidak berubah. Anak-anak lama berpindah secara implisit ke bagian bawah; hanya klasifikasi heavy pada kedua bagian yang perlu diperhitungkan, dengan paling banyak satu anak heavy pada setiap bagian. Kontraksi rantai merupakan operasi kebalikannya. Keduanya mengubah potensial hanya sebesar konstanta di luar pekerjaan access yang sudah dihitung.

Karena itu, pekerjaan struktural dengan AVL memberikan batas standar:

$$ O((n+q)\log^2 n) $$

amortized, sebelum memasukkan pekerjaan materialisasi dan traversal pelaporan.

Sebagai bentuk pembukuan yang tidak bergantung pada penyederhanaan amortized tersebut, jika $\mathcal P$ adalah banyaknya total iterasi access yang benar-benar dilakukan, pekerjaan strukturalnya adalah:

$$ O((n+q+\mathcal P)\log n). $$

19.3 Traversal, cache, dan pemanggilan pustaka

Definisikan:

• $V$: banyaknya kunjungan traversal untuk materialisasi dan pelaporan;
• $M$: banyaknya merge materialisasi langsung;
• $J$: banyaknya merge promosi;
• $R$: banyaknya laporan.

Dengan lookup hash berbiaya rata-rata $O(1)$, overhead program dapat dibukukan sebagai:

$$ O((n+q)\log^2 n+V+M+J+R). $$

Jika ingin menghilangkan asumsi lookup hash rata-rata, cache dapat diganti dengan ordered map, dengan faktor $O(\log K)$ pada operasi cache, di mana $K$ adalah banyaknya entri.

Pernyataan waktu di atas tidak boleh disederhanakan menjadi $O(q\log^2 n)$ tanpa membatasi $V,M,J,R$.

20. Analisis biaya soal Algoritma A

Pisahkan biaya menjadi:

• $I$: seluruh biaya preprocessing;
• $D$: biaya materialisasi langsung setelah preprocessing;
• $P$: biaya promosi;
• $R$: biaya laporan.

Maka identitas pembukuannya adalah:

$$ C_1=I+D+P+R. $$

20.1 Preprocessing

Preprocessing membangun:

1. segment tree himpunan berdasarkan label;
2. agregat pada AVL rantai awal;
3. agregat pada preferred path makro awal;
4. himpunan khusus $\{2,\ldots,n\}$.

Pada setiap tingkat balanced tree, jumlah bobot subtree yang tidak tumpang tindih adalah $O(n)$. Ada $O(\log n)$ tingkat.

Maka:

$$ I=O(n\log n). $$

Ini memasukkan biaya ukuran himpunan, bukan hanya banyaknya merge.

20.2 Materialisasi langsung

Setiap merge baru setelah preprocessing pada tingkat $0$ membentuk himpunan berukuran paling banyak $\beta$. Pada tingkat $1$, ukurannya paling banyak $\gamma$.

Jika jumlah merge tersebut masing-masing $M_0,M_1$, maka:

$$ D\le\beta M_0+\gamma M_1. $$

Ini adalah batas terparameterisasi yang sah. Ia belum memberikan batas numerik kecil sebelum $M_0$ dan $M_1$ sendiri dibatasi.

20.3 Promosi

Anggaran global sudah membuktikan:

$$ P\le\frac R2. $$

Sehingga:

$$ C_1 \le I+D+\frac32R. $$

Atau:

$$ C_1 \le I+\beta M_0+\gamma M_1+\frac32R. $$

Rumus ini menjelaskan apa yang harus diperhatikan saat mengukur performa:

• cache mengurangi materialisasi ulang;
• agregat kecil dan promosi mengurangi $R$;
• batas ukuran mencegah satu pembelian eager yang terlalu mahal;
• promosi mempunyai batas anggaran yang dapat dibuktikan.

20.4 Gap yang masih tersisa

Untuk membuktikan jaminan skor penuh worst-case pada subtask $2$ dan $4$, kita masih memerlukan batas seragam yang cukup kuat terhadap:

$$ M_0,\qquad M_1,\qquad R, $$

untuk seluruh urutan modifikasi legal.

Tulisan ini belum mempunyai batas tersebut yang menyimpulkan:

$$ I+\beta M_0+\gamma M_1+\frac32R \le150\,000\,000. $$

Tidak cukup menggunakan salah satu argumen berikut:

• “AVL mempunyai tinggi logaritmik.”
• “Cache biasanya sering terpakai.”
• “Interval berukuran besar pasti hanya sedikit.”
• “Penilai non-adaptif, sehingga tidak bisa memberikan kasus buruk.”
• “Implementasinya diterima, jadi batas worst-case pasti sudah terbukti.”

Secara khusus, AVL seimbang menurut tinggi, bukan menurut jumlah elemen. Kita tidak boleh langsung mengasumsikan bahwa setiap potongan maksimal berbobot paling banyak $\beta$ selalu berbobot $\Theta(\beta)$, lalu mengklaim ada $O(n/\beta)$ potongan.

Penilai non-adaptif juga tetap boleh menggunakan suatu urutan buruk yang sudah ditentukan sebelumnya.

20.5 Batas umum yang konservatif

Correctness memberikan batas sederhana:

$$ R\le nq, $$

karena setiap laporan tidak kosong, semua laporan pada satu query saling lepas, dan jalur memuat paling banyak $n$ simpul.

Dalam satu query, struktur AVL tidak lagi diubah setelah access selesai. Agregat langsung yang benar-benar dibuat berada pada subtree berbobot paling banyak $\beta$ atau $\gamma$.

Setiap simpul asli dapat berkontribusi pada penggabungan hanya sepanjang rantai leluhur dalam subtree kecil tersebut. Tinggi AVL itu adalah $O(\log(\beta+1))$ atau $O(\log(\gamma+1))$. Setiap node membentuk paling banyak dua penggabungan.

Dengan mengabaikan seluruh manfaat cache, ini memberikan batas konservatif:

$$ D= O\!\left( nq\bigl(\log(\beta+1)+\log(\gamma+1)\bigr) \right). $$

Bersama $P\le R/2$, kita memperoleh batas asimtotik yang sah, tetapi terlalu besar untuk menyimpulkan skor penuh:

$$ C_1= O\!\left( n\log n+ nq\bigl(1+\log(\beta+1)+\log(\gamma+1)\bigr) \right). $$

Manfaat cache dan bentuk rangkaian operasi membuat biaya aktual implementasi jauh lebih rendah pada pengujian yang dilaporkan. Justru manfaat inilah yang belum mempunyai batas universal cukup tajam dalam analisis di sini.

20.6 Cara menyatakan hasilnya secara akurat

Klaim yang dapat dibuat adalah:

Algoritma menghasilkan jawaban yang selalu tepat. Implementasi dengan kebijakan materialisasi, cache, dan parameter tersebut dilaporkan memperoleh 100 poin. Komponen biaya promosi mempunyai batas amortized yang terbukti. Jaminan numerik biaya total untuk semua masukan legal belum diturunkan.

Pernyataan ini tetap berguna bagi pembaca: ia membedakan teknik yang sudah terbukti dari bagian yang masih dapat dikembangkan.

21. Analisis memori Algoritma A

Array struktur kedua tingkat, segment tree label, serta buffer query menggunakan $O(n)$ ruang.

Cache dan handle himpunan yang pernah dibuat membutuhkan pembukuan terpisah.

Misalkan:

• $K$ adalah banyaknya pasangan ujung yang tersimpan pada cache;
• $M$ adalah banyaknya merge materialisasi langsung setelah preprocessing;
• $J$ adalah banyaknya merge promosi.

Implementasi menyimpan handle hasil lama, sehingga batas ruangnya adalah:

$$ O(n+K+M+J). $$

Handle $\texttt{infoset}$ berukuran tetap, tetapi jumlah handle tetap perlu diperhatikan. Handle lama tidak boleh dianggap otomatis hilang hanya karena entri cache untuk pasangan ujung yang sama ditimpa.

Oleh sebab itu, menyatakan memori seluruh Algoritma A sebagai $O(n)$ tidak akurat untuk implementasi ini.

22. Urutan inisialisasi

Urutan berikut memudahkan implementasi dan pembuktian:

1. simpan singleton;
2. simpan orang tua asli, jumlah anak, dan XOR anak;
3. bangun segment tree himpunan menurut label;
4. temukan seluruh rantai normal awal;
5. bangun AVL tingkat $0$ untuk setiap rantai;
6. tentukan orang tua setiap simpul makro;
7. hitung ukuran subtree makro berbobot;
8. pilih heavy child awal;
9. bangun AVL tingkat $1$ untuk preferred path awal;
10. aktifkan kebijakan materialisasi selektif untuk operasi berikutnya.

Karena orang tua awal memenuhi:

$$ p(i)<i, $$

beberapa perhitungan awal dapat dilakukan dengan urutan label terbalik. Setelah modifikasi, asumsi tersebut tidak boleh dipakai lagi.

Agregat awal boleh dibangun lebih lengkap daripada agregat setelah modifikasi. Biayanya dibayar sekali dan tetap masuk ke $I$.

23. Pemetaan ke implementasi

Cabang pemilihan algoritma:

$$ \begin{cases} \text{Algoritma B},&\text{subtask }1,3,5,\\ \text{Algoritma A},&\text{subtask }2,4. \end{cases} $$

Komponen Algoritma A:

Komponen Algoritma B:

24. Detail implementasi yang menentukan

24.1 Pisahkan struktur sequence dan materialisasi himpunan

Fungsi pembaruan metadata AVL tidak boleh otomatis memanggil merge untuk setiap simpul yang berubah.

Jika tidak dipisahkan, persoalan biaya linear kembali muncul meskipun logika dynamic tree sudah benar.

24.2 Cache tanpa handle belum dapat dipakai

Satu entri cache dapat hanya menyimpan kredit promosi tanpa agregat yang sudah terbentuk.

Pemeriksaan lookup harus memastikan:

$$ \text{handle tersedia} \quad\land\quad \text{timestamp valid}. $$

Timestamp valid saja tidak cukup.

24.3 Jangan tertukar antara label minimum dan endpoint

Cache jalur memakai endpoint berorientasi:

$$ (\operatorname{first},\operatorname{last}). $$

Optimasi interval label memakai:

$$ (\operatorname{minLabel},\operatorname{maxLabel},\operatorname{weight}). $$

Kedua pasangan tersebut tidak mempunyai arti yang sama.

24.4 Invalidate hanya bagian yang benar-benar terpengaruh

Mengganti orang tua $x$ memperbarui timestamp $m(x)$, lalu metadata pada jalur leluhur AVL yang terkait.

Membatalkan seluruh cache setiap modifikasi akan menghilangkan manfaat utama reuse interval.

24.5 Jangan memakai seluruh rantai LCA secara sembarang

Jika LCA makro bukan salah satu rantai ujung, hanya ujung bawah rantainya yang berada pada jalur query.

24.6 Penggabungan seimbang pada promosi

Buffer promosi berisi partisi interval, sehingga dapat digabung secara rekursif berdasarkan indeks tengah.

Rekursinya berkedalaman $O(\log k)$.

24.7 Perhatikan kedalaman rekursi pohon asli

Pohon asli bisa berupa rantai sepanjang $10^5$.

Traversal pohon asli sebaiknya iteratif. Rekursi AVL aman karena kedalamannya $O(\log n)$.

Pada Algoritma B, DFS prefix hanya berada di dalam cluster berukuran paling banyak $64$.

24.8 Gunakan bilangan 64 bit untuk biaya dan kredit

Walaupun ukuran satu himpunan paling banyak $10^5$, jumlah biaya, kredit lokal, dan anggaran global dapat jauh lebih besar.

Gunakan tipe 64 bit untuk:

$$ C_1,\ P,\ R,\ \operatorname{credit},\ \operatorname{balance}. $$

Kunci pasangan ujung juga sebaiknya menggunakan tipe 64 bit.

25. Menguji solusi tanpa tertipu grader contoh

Ada tiga jenis verifikasi yang berbeda.

25.1 Verifikasi jawaban jalur

Untuk pohon kecil:

1. simpan orang tua secara eksplisit;
2. terapkan modifikasi;
3. cari jalur query dengan algoritma sederhana;
4. bandingkan dengan gabungan seluruh himpunan yang dilaporkan.

Periksa dua syarat:

$$ \bigcup_i A_i=P(x,y) $$

dan

$$ A_i\cap A_j=\varnothing \qquad(i\ne j). $$

Tidak semua grader contoh otomatis memverifikasi bahwa himpunan yang dilaporkan benar-benar merupakan jalur yang diminta. Perbandingan dengan pembanding independen tetap diperlukan.

25.2 Verifikasi invariant internal

Pada pengujian debug, periksa:

• pointer orang tua AVL sesuai pointer anak;
• tinggi AVL dan ukuran subtree benar;
• urutan rantai sesuai hubungan orang tua asli;
• setiap simpul asli berada pada tepat satu rantai atau cluster;
• cluster tetap terhubung;
• ukuran cluster paling banyak $B$;
• setiap dua cluster bertetangga mempunyai jumlah ukuran lebih dari $B$;
• cache yang dipakai benar-benar cocok dengan interval sekarang.

25.3 Verifikasi biaya

Pisahkan penghitung:

$$ I,\quad D,\quad P,\quad R. $$

Periksa:

$$ C_1=I+D+P+R, $$

dan

$$ 2P\le R. $$

Untuk Algoritma B, setiap operasi harus memenuhi:

$$ \operatorname{cost}_{\mathrm{ask}}\le3140, \qquad \operatorname{cost}_{\mathrm{modify}}\le4158 $$

pada batas ukuran maksimum.

Pengujian biaya tidak menggantikan analisis worst-case, tetapi sangat membantu menemukan bagian implementasi yang melakukan materialisasi berlebihan.

25.4 Keluarga kasus penting

Keluarga yang berguna antara lain:

1. satu rantai panjang;
2. bintang dengan banyak daun;
3. beberapa lengan panjang;
4. pohon sisir: backbone panjang dengan daun samping;
5. pohon bercabang dengan setiap sisinya diperpanjang menjadi rantai;
6. pemotongan dan penyambungan blok rantai;
7. query dengan ujung yang selalu berubah;
8. pemindahan seluruh subtree tanpa mengubah jalur internal yang sedang di-cache;
9. pengulangan query pada interval yang sama sampai promosi terjadi;
10. perubahan satu sisi internal interval setelah promosi.

Kasus $8$ memeriksa manfaat mengecualikan timestamp simpul pertama. Kasus $10$ memeriksa bahwa cache lama tidak dipakai secara salah.

25.5 Jangan mencampur argumen acak dengan algoritma

Pengujian acak berguna untuk menemukan bug. Algoritma sendiri tidak bergantung pada keberuntungan untuk menghasilkan jawaban yang benar.

Correctness didasarkan pada invariant partisi, struktur jalur, dan validasi cache.

26. Bagaimana menemukan pendekatan ini?

Alur penalaran yang dapat dipakai pembaca adalah sebagai berikut.

Langkah A: pisahkan dua sasaran skor

Untuk $C_2$, kita ingin setiap operasi mempunyai pekerjaan himpunan yang kecil, walaupun totalnya lebih besar.

Untuk $C_1$, kita ingin biaya pembentukan himpunan dapat dipakai ulang sebanyak mungkin.

Kedua tujuan tersebut tidak harus menggunakan struktur yang sama.

Langkah B: gunakan connected cluster untuk $C_2$

Prefix cluster memberikan satu laporan untuk melewati satu cluster. Rebuild lokal mempunyai batas kuadratik terhadap ukuran cluster.

Invariant:

$$ |U|+|V|>B $$

mengubah ukuran lokal menjadi batas global atas jumlah cluster pada jalur.

Inilah inti pembuktian $C_2$.

Langkah C: kenali bahwa rantai adalah sumber biaya rebuild besar

Pada pohon hampir berupa rantai, pemecahan preferred path dapat merusak banyak agregat besar walaupun hubungan asli hanya berubah sedikit.

Pisahkan rantai tanpa percabangan dari struktur percabangannya.

Langkah D: pertahankan identitas interval

Bentuk binary tree internal bisa berubah, tetapi interval jalurnya sering tetap sama. Cache berdasarkan endpoint memanfaatkan identitas matematis tersebut.

Timestamp sisi internal menjadikan reuse ini aman setelah modifikasi.

Langkah E: jangan membeli semua agregat

Materialisasikan bagian kecil. Untuk bagian yang lebih mahal, tunggu pemakaian berulang dan gunakan anggaran promosi.

Langkah F: audit setiap klaim kompleksitas

Untuk setiap pernyataan “murah”, tanyakan:

$$ \text{Murah dalam waktu CPU, banyak panggilan, atau biaya soal?} $$

Untuk setiap klaim “amortized”, tentukan:

• potensial atau kredit yang digunakan;
• peristiwa yang menambahnya;
• peristiwa yang menguranginya;
• komponen biaya yang benar-benar dibatasi;
• komponen biaya yang belum tercakup.

Pada soal ini, audit tersebut sama pentingnya dengan memilih dynamic tree.

27. Pernyataan hasil per subtask

Subtask 1

Singleton sudah cukup:

$$ C_1\le nq\le10^4. $$

Ada pembuktian penuh bahwa ambang skor penuh dipenuhi.

Subtask 2

Pohon terdiri dari lengan-lengan. Algoritma A mereduksi persoalannya menjadi split, concatenate, dan query interval rantai, dengan cache serta materialisasi selektif.

Correctness terbukti. Implementasinya dilaporkan memperoleh skor penuh. Batas numerik universal $C_1\le150$ juta untuk kebijakan tersebut belum dibuktikan dalam tulisan ini.

Subtask 3

Gunakan Algoritma B, tanpa perlu memanfaatkan syarat bentuk pohon:

$$ C_2\le4158<5000. $$

Ada pembuktian penuh bahwa ambang skor penuh dipenuhi.

Subtask 4

Gunakan Algoritma A lengkap:

$$ \text{rantai normal} + \text{preferred path makro} + \text{AVL} + \text{cache timestamp} + \text{materialisasi selektif} + \text{promosi beranggaran}. $$

Correctness terbukti. Pembukuan biaya memberikan:

$$ C_1\le I+D+\frac32R. $$

Implementasinya dilaporkan memperoleh skor penuh. Batas worst-case numerik terhadap $D$ dan $R$ masih merupakan gap analisis.

Subtask 5

Gunakan Algoritma B:

$$ \operatorname{ask}\le3140, \qquad \operatorname{modify}\le4158, $$

sehingga:

$$ C_2\le4158<5000. $$

Ada pembuktian penuh bahwa ambang skor penuh dipenuhi.

28. Catatan untuk penerbitan

Bagian yang sudah dapat dipublikasikan sebagai teorema adalah:

1. correctness seluruh algoritma;
2. batas $C_2$ Algoritma B;
3. validitas cache timestamp;
4. validitas reuse berdasarkan interval label;
5. batas biaya promosi $P\le R/2$;
6. pembukuan biaya $C_1=I+D+P+R$.

Bagian yang perlu dilabeli sebagai kebijakan implementasi yang lolos pengujian adalah pemilihan parameter dan penggunaan cache/materialisasi untuk mencapai ambang $C_1$ pada subtask $2$ dan $4$.

Pengembangan teoritis yang masih diperlukan adalah sebuah batas terhadap pembentukan agregat langsung dan jumlah laporan pada semua urutan operasi legal, cukup kuat untuk menurunkan:

$$ C_1\le1.5\cdot10^8. $$

Menemukan batas tersebut, atau mengganti kebijakan materialisasi dengan varian yang mempunyai batas eksplisit, akan menutup gap antara implementasi 100 poin dan solusi dengan jaminan skor penuh worst-case.