网站开发 居易国际,网站怎样优化seo,大石桥网站制作,如何做好一个营销方案文章目录1. 概念2. 建树3. 查询4. 修改5. 完整代码及测试上图 from 熊掌搜索 类似数据结构#xff1a;树状数组
1. 概念
线段树是一种二叉树#xff0c;是用来表示一个区间的树#xff1a;
常常用来查询区间的#xff1a;和、最小值、最大值树结点中存放不是普通二叉树的…
文章目录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(vectorint 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,mid1,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(logn)O(\log n)O(logn) vectorint query(TreeNode *rt, int s, int e)//查询区间的summinmax{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};//完全包含区间取其值//不完全包含左右查找vectorint l query(rt-left, s, e);vectorint r query(rt-right,s, e);//汇总信息vectorint 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(logn)O(\log n)O(logn) 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/*/
#includevector
#includeiostream
#includeclimits
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;vectorint data;SegmentTree(vectorint 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(vectorint 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,mid1,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;}vectorint query(TreeNode *rt, int s, int e)//查询区间的summinmax{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};//完全包含区间取其值//不完全包含左右查找vectorint l query(rt-left, s, e);vectorint r query(rt-right,s, e);//汇总信息vectorint 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(vectorint a)
{for(auto ai : a)cout ai ;cout endl;
}int main()
{vectorint v {1,2,7,8,5};printVec(v);cout 建立线段树 endl;SegmentTree sgtree(v);printVec(sgtree.data);cout 查询区间的sumMINMAX endl;vectorint qy_res sgtree.query(sgtree.root,1,3);printVec(qy_res);cout 修改某位置的值 endl;sgtree.modify(sgtree.root,1,100);printVec(sgtree.data);cout 查询区间的sumMINMAX 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 GPLd, 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
查询区间的sumMINMAX
17 2 8
修改某位置的值
1 100 7 8 5
查询区间的sumMINMAX
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. 区间求和 IIhard
