文章目錄

• • 1. 概念
  • 2. 建樹
  • 3. 查詢
  • 4. 修改
  • 5. 完整代碼及測試

上圖 from 熊掌搜索

• 類似數據結構：樹狀數組

1. 概念

線段樹是一種二叉樹，是用來表示一個區間的樹：

• 常常用來查詢區間的：和、最小值、最大值
• 樹結點中存放不是普通二叉樹的值，其結點結構如下

class TreeNode { public:int sum;//區間和int MAX;//區間最大的int MIN;//區間最小的int start, end;//區間左右端點TreeNode *left, *right;//左右節點TreeNode(int s, int e, int v):start(s),end(e),sum(v){left = right = NULL;MAX = v;MIN = v;} };

2. 建樹

• 傳入數組，及其左右極限端點
• 自底向上建樹

TreeNode* build(vector<int>& A, int L, int R){if(L > R)return NULL;TreeNode* rt = new TreeNode(L,R,A[L]);if(L == R)return rt;int mid = L+((R-L)>>1);//對半分開rt->left = build(A,L,mid);rt->right = build(A,mid+1,R);rt->sum = 0;if(rt->left){rt->sum += rt->left->sum;rt->MAX = max(rt->MAX, rt->left->MAX);rt->MIN = min(rt->MIN, rt->left->MIN);}if(rt->right){rt->sum += rt->right->sum;rt->MAX = max(rt->MAX, rt->right->MAX);rt->MIN = min(rt->MIN, rt->right->MIN);}return rt;}

3. 查詢

• 時間復雜度：$O(\log n)$

vector<int> query(TreeNode *rt, int s, int e)//查詢區間的sum，min，max{if(s > rt->end || e < rt->start)return {0, INT_MAX, INT_MIN};//沒有交集if(s <= rt->start && rt->end <= e)return {rt->sum, rt->MIN, rt->MAX};//完全包含區間，取其值//不完全包含，左右查找vector<int> l = query(rt->left, s, e);vector<int> r = query(rt->right,s, e);//匯總信息vector<int> summary(3);summary[0] = l[0] + r[0];summary[1] = min(l[1], r[1]);summary[2] = max(l[2], r[2]);return summary;}

4. 修改

• 時間復雜度：$O(\log n)$

void modify(TreeNode *rt, int id, int val){if(rt->start == rt->end){ //葉子節點rt->sum = val;//和為自身rt->MAX = val;rt->MIN = val;data[id] = val;return;}int mid = (rt->start + rt->end)/2;if(id > mid)modify(rt->right, id, val);elsemodify(rt->left, id, val);root->sum = 0;if(rt->left){rt->sum += rt->left->sum;rt->MAX = max(rt->MAX, rt->left->MAX);rt->MIN = min(rt->MIN, rt->left->MIN);}if(rt->right){rt->sum += rt->right->sum;rt->MAX = max(rt->MAX, rt->right->MAX);rt->MIN = min(rt->MIN, rt->right->MIN);}}

5. 完整代碼及測試

/*** @description: 線段樹* @author: michael ming* @date: 2020/3/13 0:21* @modified by:* @Website: https://michael.blog.csdn.net/*/ #include<vector> #include<iostream> #include<climits> using namespace std; class TreeNode { public:int sum;//區間和int MAX;//區間最大的int MIN;//區間最小的int start, end;//區間左右端點TreeNode *left, *right;//左右節點TreeNode(int s, int e, int v):start(s),end(e),sum(v){left = right = NULL;MAX = v;MIN = v;} }; class SegmentTree { public:TreeNode* root;vector<int> data;SegmentTree(vector<int>& A){root = build(A, 0, A.size()-1);data = A;}~SegmentTree(){destroy(root);}void destroy(TreeNode* rt){if(!rt) return;destroy(rt->left);destroy(rt->right);delete rt;}TreeNode* build(vector<int>& A, int L, int R){if(L > R)return NULL;TreeNode* rt = new TreeNode(L,R,A[L]);if(L == R)return rt;int mid = L+((R-L)>>1);//對半分開rt->left = build(A,L,mid);rt->right = build(A,mid+1,R);rt->sum = 0;if(rt->left){rt->sum += rt->left->sum;rt->MAX = max(rt->MAX, rt->left->MAX);rt->MIN = min(rt->MIN, rt->left->MIN);}if(rt->right){rt->sum += rt->right->sum;rt->MAX = max(rt->MAX, rt->right->MAX);rt->MIN = min(rt->MIN, rt->right->MIN);}return rt;}vector<int> query(TreeNode *rt, int s, int e)//查詢區間的sum，min，max{if(s > rt->end || e < rt->start)return {0, INT_MAX, INT_MIN};//沒有交集if(s <= rt->start && rt->end <= e)return {rt->sum, rt->MIN, rt->MAX};//完全包含區間，取其值//不完全包含，左右查找vector<int> l = query(rt->left, s, e);vector<int> r = query(rt->right,s, e);//匯總信息vector<int> summary(3);summary[0] = l[0] + r[0];summary[1] = min(l[1], r[1]);summary[2] = max(l[2], r[2]);return summary;}void modify(TreeNode *rt, int id, int val){if(rt->start == rt->end){ //葉子節點rt->sum = val;//和為自身rt->MAX = val;rt->MIN = val;data[id] = val;return;}int mid = (rt->start + rt->end)/2;if(id > mid)modify(rt->right, id, val);elsemodify(rt->left, id, val);root->sum = 0;if(rt->left){rt->sum += rt->left->sum;rt->MAX = max(rt->MAX, rt->left->MAX);rt->MIN = min(rt->MIN, rt->left->MIN);}if(rt->right){rt->sum += rt->right->sum;rt->MAX = max(rt->MAX, rt->right->MAX);rt->MIN = min(rt->MIN, rt->right->MIN);}} }; //-------------test--------------------- void printVec(vector<int> &a) {for(auto& ai : a)cout << ai << " ";cout << endl; }int main() {vector<int> v = {1,2,7,8,5};printVec(v);cout << "建立線段樹" << endl;SegmentTree sgtree(v);printVec(sgtree.data);cout << "查詢區間的sum，MIN，MAX" << endl;vector<int> qy_res = sgtree.query(sgtree.root,1,3);printVec(qy_res);cout << "修改某位置的值" << endl;sgtree.modify(sgtree.root,1,100);printVec(sgtree.data);cout << "查詢區間的sum，MIN，MAX" << endl;qy_res = sgtree.query(sgtree.root,1,3);printVec(qy_res);return 0; }

運行結果：valgrind ./a.out

==16895== Memcheck, a memory error detector ==16895== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==16895== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info ==16895== Command: ./a.out ==16895== 1 2 7 8 5 建立線段樹 1 2 7 8 5 查詢區間的sum，MIN，MAX 17 2 8 修改某位置的值 1 100 7 8 5 查詢區間的sum，MIN，MAX 115 7 100 ==16895== ==16895== HEAP SUMMARY: ==16895== in use at exit: 0 bytes in 0 blocks ==16895== total heap usage: 29 allocs, 29 frees, 616 bytes allocated ==16895== ==16895== All heap blocks were freed -- no leaks are possible ==16895== ==16895== For counts of detected and suppressed errors, rerun with: -v ==16895== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

• 相關題目：LintCode 207. 區間求和 II（hard）

總結

以上是生活随笔為你收集整理的数据结构--树--线段树（Segment Tree）的全部內容，希望文章能夠幫你解決所遇到的問題。

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