問題提出：
現有如下的問題，給定一個的序列，實現以下操作：
①更新序列的某個值。
②查詢序列的某個區間的最小值(最大值、區間和)線段樹常用於解決區間統計問題。求最值，區間和等操作均可使用該數據結構，本篇以求最小值為例。
③更新序列的某個區間內的所有值。
對於求最小值，我們很容易想到的算法就是。更新序列的某個值直接找到該值，更新，時間復雜度是O(1)；區間查詢直接遍歷該區間，時間復雜度是O(n)；區間修改的也是直接遍歷該區間修改，時間復雜度是O(n)，在數據量特別大，操作比較多的時候，效率是很低的。另一種解法是這樣的。構建一個二維數組，a[i][j]表示區間[i,j]的最小值。這樣查詢操作的復雜度為O(1)，但是這樣的話，修改的復雜度也不低而且如果數據量特別大，O(n^2)的空間復雜度也是不容忽視的。這時候就需要我們是用線段樹這種優秀的高級數據結構來解決瞭。
線段樹：
我們以序列{5,9,7,4,6,1}為例子演示。這個序列構成的線段樹是這樣的。
從這顆樹上我們可以瞭解線段樹的這幾個特點，線段樹是一顆近似的完全二叉樹，每個節點代表一個區間，節點的權值是該區間的最小值。根節點是整個區間。每個節點的左孩子是該節點所代表的的區間的左半部分，右孩子是右半部分。為方便起見，如果區間長度為奇數，則左孩子為較長的半部分。通過線段樹，我們可以用O(logn)的時間復雜度完成查詢和更新操作。當然，預處理的時間復雜度是O(n)。
線段樹的構建：
我們將每一個節點封裝到Node類中。
class Node//節點
{
int start;//區間的左端點
int end;//區間的右端點
int data;//該節點的值
int mark = 0;//延遲更新的標記
public Node(int start,int end)//構造方法中傳入左端點和右端點
{
this.start = start;
this.end = end;
}
void addMark(int value)//做標記
{
this.mark+=value;
}
void clearMark()
{
this.mark = 0;
}
public String toString()
{
return start+"-"+end;
}
}