/ taohigo.com / 0浏览

史上最詳細的線段樹教程

問題提出:

現有如下的問題,給定一個的序列,實現以下操作:

①更新序列的某個值。

②查詢序列的某個區間的最小值(最大值、區間和)線段樹常用於解決區間統計問題。求最值,區間和等操作均可使用該數據結構,本篇以求最小值為例。

③更新序列的某個區間內的所有值。

對於求最小值,我們很容易想到的算法就是。更新序列的某個值直接找到該值,更新,時間復雜度是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;
}
}

由淺入深認識黑頭、白頭
由淺入深認識黑頭、白頭
同工同酬!昆明經濟技術開發區招聘教師182人
選調生總結2022.6.27 褪去“書生氣”,沾滿“泥土香”
選調生總結2022.6.27 褪去“書生氣”,沾滿“泥土香”
4000字深度剖析 | “一書三證”的前世今生
4000字深度剖析 | “一書三證”的前世今生
我的傢庭史
瓢蟲
瓢蟲

0

  1. This post has no comment yet

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注