--------------------------------------------不是能不能辦到的問題，既然我已經下定決心要成為海賊王了，如果因此而戰死的話，也無所謂了。

承接上一章節，繼續探索線段樹丫！

如何利用線段樹進行區間統計?

假設這13個數為1,2,3,4,1,2,3,4,1,2,3,4,1. （A[1]=1,A[2]=2,......A[13]=1）在區間之后標上該區間的數字之和：

?

?

如果要計算[2,12]的和，按照之前的算法：

?

[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12]

?

? 29 ?= 2 + 7 + 6 + 7 + 7

?

計算5個數的和就可以算出[2,12]的值。

?嘻嘻，下面介紹另一個問題:

如何進行點修改?

以上一個圖為討論的基礎:

假設把A[6]+=7 ,看看哪些區間需要修改？[6],[5,6],[5,7],[1,7],[1,13]這些區間全部都需要+7.其余所有區間都不用動。

于是，這顆線段樹中，點修改最多修改5個線段樹元素（每層一個）。

下圖中，修改后的元素用藍色表示。

?

一身轉戰三千里，且去追尋線段樹的存儲結構:

線段樹是一種二叉樹，當然可以像一般的樹那樣寫成結構體，指針什么的。 但是它的優點是， 它也可以用數組來實現樹形結構，可以大大簡化代碼。 數組形式適合在編程競賽中使用，在已經知道線段樹的最大規模的情況下，直接開足夠空間的數組，然后在上面建立線段樹。 簡單的記法： 足夠的空間 = 數組大小n的四倍。 實際上足夠的空間 =? （n向上擴充到最近的2的某個次方）的兩倍。 舉例子：假設數組長度為5，就需要5先擴充成8，8*2=16.線段樹需要16個元素。如果數組元素為8，那么也需要16個元素。
所以線段樹需要的空間是n的兩倍到四倍之間的某個數，一般就開4*n的空間就好，如果空間不夠，可以自己算好最大值來省點空間。 怎么用數組來表示一顆二叉樹呢？假設某個節點的編號為v,那么它的左子節點編號為2*v，右子節點編號為2*v+1。 然后規定根節點為1.這樣一顆二叉樹就構造完成了。通常2*v在代碼中寫成 v<<1 。 2*v+1寫成 v<<1|1 。

轉載于:https://www.cnblogs.com/dragondragon/p/11241773.html

總結

以上是生活随笔為你收集整理的线段树入门之夜空星亮的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。