在線段樹中，一般都不需要刻意保存其左右子結(jié)點(diǎn)的下標(biāo)，而直接由其本身的下標(biāo)導(dǎo)出，傳統(tǒng)的寫法是：
根結(jié)點(diǎn)：1
A的左子結(jié)點(diǎn)：2A（寫成A<<1）
A的右子結(jié)點(diǎn)：2A+1（寫成(A<<1)+1）
這種表示法可以表示出整棵線段樹，因?yàn)椋?br />（1）每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)的下標(biāo)都比它大，這樣就不會(huì)出現(xiàn)環(huán)；
（2）每個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)都是唯一的（其本身下標(biāo)整除2）；
但是，這種表示法有一個(gè)弱點(diǎn)：結(jié)點(diǎn)的下標(biāo)是有可能超過2N的，但不會(huì)超過4N，因此，為了表示出跨度為N的線段，我們需要開4N的空間，然而，其中只有2N-1個(gè)位置是有用的（因?yàn)楸硎究缍葹镹的線段的線段樹共有(2N-1)個(gè)結(jié)點(diǎn)），
這樣，就有一半的空間被浪費(fèi)。尤其是這種線段樹推廣到多維的時(shí)候——K維線段樹就只有1/2
K的位置是有用的，空間利用率非常低。在某些卡空間的場(chǎng)合，它就囧掉了。
那么，有木有好一點(diǎn)的寫法呢？最好能使空間利用率達(dá)到100%——也就是所有結(jié)點(diǎn)的下標(biāo)剛好就是1~(2N-1)！！（0號(hào)結(jié)點(diǎn)一般作為“哨兵”，不被占用）
并且，這種寫法要保證僅僅由結(jié)點(diǎn)的下標(biāo)和它表示的線段的左右端點(diǎn)（因?yàn)樵诒闅v線段時(shí)，下標(biāo)和左右端點(diǎn)基本上都是同時(shí)知道的），就能得出其子結(jié)點(diǎn)的下標(biāo)，而不需要借助額外的東東（最好mid都不需要算）。
這種寫法就是——
直接將每個(gè)結(jié)點(diǎn)的DFS遍歷次序當(dāng)做它的下標(biāo)！！
比如，跨度為6的線段樹：
容易發(fā)現(xiàn)，根結(jié)點(diǎn)下標(biāo)為1，下標(biāo)為A的結(jié)點(diǎn)的左子結(jié)點(diǎn)下標(biāo)為(A+1)，右子結(jié)點(diǎn)下標(biāo)為A+SZ(A.L)+1，其中SZ(A.L)為A的左子樹大小。
若A的左右端點(diǎn)為l、r，mid=(l+r)/2（下取整），則A的左子樹所表示的線段為[l, mid]，所以SZ(A.L)=(mid-l+1)*2-1=(mid-l)*2+1=((r-l-1)/2（上取整）)*2+1
這樣，A的右子結(jié)點(diǎn)下標(biāo)就是A+((r-l+1)/2（上取整))*2，也就是
A加上大于(r-l)的最小的偶數(shù)；
寫在代碼里就是：
int mid=l+r>>1;
opr(l, mid, A+1);
opr(mid+1, r, (r-l&1?A+r-l+1:A+r-l+2));
或者，借助位運(yùn)算，可以免去條件判斷：
int mid=l+r>>1;
opr(l, mid, A+1);
opr(mid+1, r, A+r-l+2-((r^l)&1));
經(jīng)測(cè)試，后者（使用位運(yùn)算的）雖然總的運(yùn)算次數(shù)多于前者（使用條件判斷的），但后者比前者快一點(diǎn)點(diǎn)，其原因可能與C語言中的條件運(yùn)算符速度較慢有關(guān)；
這樣，我們就成功地將線段樹下標(biāo)的空間利用率提高到了100%！！以后只需要開2N空間就行了囧……
與傳統(tǒng)表示法相比，這種新式表示法雖然可以節(jié)省空間，但時(shí)間消耗要更大一些（時(shí)間和空間總是矛盾的囧……），因?yàn)樗谡矣易咏Y(jié)點(diǎn)的時(shí)候需要較多的運(yùn)算。平均起來，新式表示法比傳統(tǒng)表示法要慢10~15%，對(duì)于某些坑爹的數(shù)據(jù)（對(duì)右子結(jié)點(diǎn)調(diào)用比較多的那種）可能慢得更多。此外，在下放標(biāo)記的時(shí)候，傳統(tǒng)表示法只需要知道結(jié)點(diǎn)下標(biāo)就行了，而新式表示法必須同時(shí)知道結(jié)點(diǎn)的左右端點(diǎn)，這樣在dm中就需要傳遞三個(gè)參數(shù)，從而要慢一些，當(dāng)然，我們可以不用dm，直接在操作里面寫標(biāo)記下放。