Struktur data untuk peta pada interval

Biarkan menjadi bilangan bulat, dan biarkan menunjukkan set semua bilangan bulat. Biarkan menunjukkan interval bilangan bulat .$n$$\mathbb{Z}$$[a,b]$$\{a,a+1,a+2,\dots,b\}$

Saya mencari struktur data untuk mewakili peta . Saya ingin struktur data mendukung operasi berikut:$f:[1,n] \to \mathbb{Z}$

• $\text{get}(i)$ harus mengembalikan .$f(i)$

• $\text{set}([a,b],y)$ harus memperbarui sehingga , yaitu, memperbarui ke peta baru sedemikian rupa sehingga f ′ ( i ) = y untuk i ∈ [ a , b ] dan f ′ ( i ) = f ( i ) untuk i ∉ [ a , b ] .$f$$f(a)=f(a+1)=\cdots=f(b)=y$$f$$f'$$f'(i) = y$$i \in [a,b]$$f'(i) = f(i)$$i \notin [a,b]$

• $\text{stab}(i)$ harus mengembalikan interval terbesar sedemikian sehingga dan konstan pada (yaitu, ).$[a,b]$$i \in [a,b]$$f$$[a,b]$$f(a)=f(a+1)=\cdots=f(b)$

• $\text{add}([a,b],\delta)$ harus memperbarui ke peta baru sedemikian rupa sehingga untuk dan untuk .$f$$f'$$f'(i) = f(i) + \delta$$i \in [a,b]$$f'(i) = f(i)$$i \notin [a,b]$

Saya ingin masing-masing operasi ini menjadi efisien. Saya akan menghitung waktu atau sebagai efisien, tetapi waktu terlalu lambat. Tidak apa-apa jika waktu berjalan diamortisasi waktu berjalan. Apakah ada struktur data yang secara bersamaan membuat semua operasi ini efisien?$O(1)$$O(\lg n)$$O(n)$

(Saya perhatikan pola yang sama muncul dalam beberapa tantangan pemrograman. Ini adalah generalisasi yang cukup untuk semua masalah tantangan tersebut.)

Saya percaya waktu logaritmik untuk semua pertanyaan dapat dicapai. Gagasan utamanya adalah menggunakan pohon interval, di mana setiap node di pohon sesuai dengan interval indeks. Saya akan membangun ide-ide kunci dengan memulai dengan versi yang lebih sederhana dari struktur data (yang dapat mendukung pengaturan dan bukan operasi lainnya), kemudian menambahkan fitur untuk mendukung fitur-fitur lainnya juga.

Skema sederhana (mendukung dapatkan dan atur, tetapi tidak menambah atau menusuk)

Katakanlah bahwa interval adalah datar jika fungsi f adalah konstan pada [ a , b ] , yaitu, jika f ( a ) = f ( a + 1 ) = ⋯ = f ( b ) .$[a,b]$$f$$[a,b]$$f(a)=f(a+1)=\cdots =f(b)$

Struktur data sederhana kami akan menjadi pohon interval. Dengan kata lain, kita memiliki pohon biner, di mana setiap node bersesuaian dengan interval (indeks). Kami akan menyimpan interval di setiap simpul v pohon. Setiap daun akan sesuai dengan interval datar, dan mereka akan diatur sehingga membacakan daun kiri-ke-kanan memberi kita urutan interval datar berturut-turut yang terpisah dan yang penyatuan semua [ 1 , n ] . Interval untuk simpul internal adalah penyatuan interval kedua anaknya. Juga, di setiap simpul daun ℓ kami akan menyimpan nilai V ( ℓ $I(v)$$v$$[1,n]$$\ell$$V(\ell)$dari fungsi pada interval I ( ℓ ) yang sesuai dengan simpul ini (perhatikan bahwa interval ini datar, sehingga f konstan pada interval tersebut, jadi kami hanya menyimpan nilai tunggal f di setiap simpul daun).$f$$I(\ell)$$f$$f$

Secara ekuivalen, Anda dapat membayangkan bahwa kita mempartisi ke dalam interval datar, dan kemudian struktur data adalah pohon pencarian biner di mana kunci adalah titik akhir kiri dari interval tersebut. Daun mengandung nilai f pada beberapa rentang indeks di mana f adalah konstan.$[1,n]$$f$$f$

Gunakan metode standar untuk memastikan bahwa pohon biner tetap seimbang, yaitu kedalamannya adalah (di mana m menghitung jumlah daun saat ini di pohon). Tentu saja, m ≤ n , jadi kedalaman selalu paling banyak O ( lg n ) . Ini akan sangat membantu di bawah ini.$O(\lg m)$$m$$m\le n$$O(\lg n)$

Kami sekarang dapat mendukung operasi get dan set sebagai berikut:

• mudah: kita melintasi pohon untuk menemukan daun yang intervalnya berisi i . Ini pada dasarnya hanya melintasi pohon pencarian biner. Karena kedalamannya adalah O ( lg n ) , waktu lari adalah O ( lg n ) .$\text{get}(i)$$i$$O(\lg n)$$O(\lg n)$

• lebih rumit. Ini berfungsi seperti ini:$\text{set}([a,b],y)$

  1. Pertama, kami menemukan interval daun mengandung a ; jika a 0 < a , maka kita membagi interval daun ini menjadi dua interval [ a 0 , a - 1 ] dan [ a , b 0 ] (sehingga mengubah simpul daun ini menjadi simpul internal dan memperkenalkan dua anak).$[a_0,b_0]$$a$$a_0 < a$$[a_0,a-1]$$[a,b_0]$

  2. Selanjutnya, kami menemukan interval daun mengandung b ; jika b < b 1 , kami membagi interval daun ini menjadi dua interval [ a 1 , b ] dan [ b + 1 , b 1 ] (sehingga mengubah simpul daun ini menjadi simpul internal dan memperkenalkan dua anak).$[a_1,b_1]$$b$$b < b_1$$[a_1,b]$$[b+1,b_1]$

  3. Pada titik ini, saya mengklaim bahwa interval dapat dinyatakan sebagai penyatuan terpisah dari interval O ( lg n ) yang sesuai dengan beberapa subset dari simpul O ( lg n ) di pohon. Jadi, hapus semua turunan dari simpul tersebut (ubah menjadi daun) dan tetapkan nilai yang disimpan di simpul tersebut menjadi y .$[a,b]$$O(\lg n)$$O(\lg n)$$y$

  4. Akhirnya, karena kami memodifikasi bentuk pohon, kami akan melakukan rotasi yang diperlukan untuk menyeimbangkan kembali pohon (menggunakan teknik standar apa pun untuk menjaga keseimbangan pohon).

  $O(\lg n)$$O(\lg n)$$O(\lg n)$

$O(\lg n)$$O(\lg \min(n,s))$$s$

Menambahkan dukungan untuk tambah

Kami dapat memodifikasi struktur data di atas sehingga juga dapat mendukung operasi penambahan. Secara khusus, alih-alih menyimpan nilai fungsi dalam daun, itu akan direpresentasikan sebagai jumlah angka yang disimpan dalam satu set node.

$f(i)$$i$$i$$v$$V(v)$$v_0,v_1,\dots,v_k$$v_k$$I(v_k)$$V(v_0)+\dots + V(v_k)$

$x$$x$

$\text{add}([a,b],\delta)$$[a,b]$$O(\lg n)$$O(\lg n)$$\delta$$O(\lg n)$node. (Kami tidak menghapus keturunan mereka.)

$O(\lg n)$$O(\lg \min(n,s))$$s$

Mendukung operasi penikaman

Permintaan penusukan adalah yang paling menantang untuk didukung. Gagasan dasarnya adalah mengubah struktur data di atas untuk mempertahankan invarian tambahan berikut:

$I(\ell)$$\ell$

$[a,b]$$[a,b]$$[a,b]$$a',b'$$1 \le a' \le a \le b \le b' \le n$$[a',b']=[a,b]$$[a',b']$

Ini membuat operasi tusukan mudah diimplementasikan:

• $\text{stab}(i)$$i$

$f$$f$$12=O(1)$$O(\lg n)$

$O(\lg n)$$O(\lg \min(n,s))$$s$

Berpisah pikiran

Fiuh, ini skema yang cukup rumit. Saya harap saya tidak membuat kesalahan. Silakan periksa pekerjaan saya dengan cermat sebelum mengandalkan solusi ini.