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