南通网站推广优化公司,成都企业网站建设那家好,wordpress 检测插件,南宁网红打卡地有哪些地方数据结构-线段树#xff08;点修区查#xff09; 前置知识
分治递归二叉树 思路
我们需要维护一个支持单点修改#xff0c;区间查询的数据结构#xff0c;并且要求在线#xff0c;一般使用线段树解决。 线段树是一个二叉树形的数据结构。 线段树的思想很简单#xff0c…数据结构-线段树点修区查 前置知识
分治递归二叉树 思路
我们需要维护一个支持单点修改区间查询的数据结构并且要求在线一般使用线段树解决。 线段树是一个二叉树形的数据结构。 线段树的思想很简单就是将每个区间分治构成一个树形结构从而达到了 log n \log n logn 的时间复杂度。 以下是一个维护最小值的线段树。 具体实现也很简单如下
建树 build \text{build} build 从根节点向下遍历叶节点自更新非叶节点使用儿子节点更新 pushup \text{pushup} pushup更新 update \text{update} update 从根节点向下遍历类似二分查找查找至叶结点叶节点自更新非叶节点使用儿子节点更新 pushup \text{pushup} pushup查询 query \text{query} query 从根节点向下遍历将区间分治到多个节点上合并答案。如区间 [ 2 , 6 ] [ 2 , 3 ] [ 4 , 5 ] [ 6 , 6 ] [2,6][2,3][4,5][6,6] [2,6][2,3][4,5][6,6]为节点 5 , 6 , 14 5,6,14 5,6,14 处的答案合并而来。 数据结构参数
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)空间复杂度 O ( n ) O(n) O(n) 实现代码
以最小值线段树为例。
int t[MAXN*4];
#define ls p1
#define rs p1|1
void pushup(int p){t[p]min(t[ls],t[rs]);
}
void build(int p,int l,int r){if (lr){t[p]a[l];return;}int midlr1;build(ls,l,mid);build(rs,mid1,r);pushup(p);
}
void update(int p,int l,int r,int x,int y){if (lr){t[p]y;return;}int midlr1;if (xmid) update(ls,l,mid,x,y);else update(rs,mid1,r,x,y);pushup(p);
}
int query(int p,int l,int r,int x,int y){if (xlry) return t[p];int midlr1,ans0x3f3f3f3f;if (xl) ansmin(ans,query(ls,l,mid,x,y));else ansmin(ans,query(rs,mid1,r,x,y));return ans;
}练习
洛谷【模板】树状数组 1洛谷【模板】树状数组 2 因为这个版本的线段树和树状数组差不多。。。
