被感情傷害后弱弱地更新一篇題解。

平衡樹(shù)板子題，正常建樹(shù)，節(jié)點(diǎn)的權(quán)值就是書(shū)的編號(hào)。對(duì)于插入，有個(gè)小 trick，就是假設(shè)插入的位置為 ，那么可以將第? 個(gè)節(jié)點(diǎn)伸展到樹(shù)根位置，繼續(xù)把平衡樹(shù)的第 ?個(gè)節(jié)點(diǎn)伸展到根節(jié)點(diǎn)的左子樹(shù)，顯然第 ?個(gè)節(jié)點(diǎn)的右子樹(shù)一定為空，這時(shí)候把新來(lái)的節(jié)點(diǎn)插在這個(gè)位置。當(dāng)然對(duì)于最后一個(gè)詢(xún)問(wèn)，直接查第 ?個(gè)節(jié)點(diǎn)即可。

Code: