2. IT
    3. 【线段树】 求区间最小值以及区间最小值

    【线段树】 求区间最小值以及区间最小值

    xiaoxiao2021-04-14  36
    //结构体数组建树，求区间最小值，单点更新最小值 #include<stdio.h> #define MAX 65535 #define INFINITY 65535 #define min(a,b) a<b?a:b struct Node { int val; }segtree[MAX]; void buildtree(int root, int arr[],int istart,int iend ) { if(istart==iend)//叶子节点 segtree[root].val=arr[istart]; else { buildtree(root*2+1,arr,istart,(istart+iend)/2);//递归构造左子树 buildtree(root*2+2,arr,(istart+iend)/2+1,iend);//递归构造右子树 segtree[root].val=min(segtree[root*2+1].val,segtree[root*2+2].val);//更新根节点的值 } } int query(int root,int arr[],int start,int end,int qstart ,int qend) //区间查询 { if(qstart>end||qend<start) return INFINITY;//当前节点区间与查询区间没有交集 if(qstart<=start&&qend>=end) return segtree[root].val;//查询区间包含当前节点区间 else { return min(query(root*2+1,arr,start,(start+end)/2,qstart,qend),query(root*2+2,arr,(start+end)/2+1,end,qstart,qend)); }//返回左右子树查询的最小值 } void update(int root ,int start,int end,int index,int addval)//单点更新 { if(start==end) { if(start==index) //找到更新的节点 segtree[root].val+=addval; return ; } int mid=(start+end)/2; if(index<=mid)//在左子树中更新 update(root*2+1,start,mid,index,addval); else update(root*2+2,mid+1,end,index,addval); segtree[root].val=min(segtree[root*2+1].val,segtree[root*2+2].val); // 根据左右子树的值回溯更新当前节点的值 } int main() { int a[]={3,4,5,7,2,1,0,3,4,5}; buildtree(1,a,0,9); int t=query(1,a,0,9,0,6); printf("%d\n",t); update(1,0,9,6,1); int tt=query(1,a,0,9,0,6); //printf("%d",sizeof(a)/sizeof(a[0])-1); return 0; }   //简单数组建树查询操作，求区间最小值下标 #include<iostream> #include<string.h> using namespace std; #define MAXN 100 #define MAXIND 256 //线段树节点个数 //构建线段树,目的:得到M数组. void build(int node, int b, int e, int M[], int A[]) { if (b == e) M[node] = b; //只有一个元素,只有一个下标 else { build(2 * node, b, (b + e) / 2, M, A); build(2 * node + 1, (b + e) / 2 + 1, e, M, A); if (A[M[2 * node]] <= A[M[2 * node + 1]]) M[node] = M[2 * node]; else M[node] = M[2 * node + 1]; } } //找出区间 [i, j] 上的最小值的索引 int query(int node, int b, int e, int M[], int A[], int i, int j) { int p1, p2; //查询区间和要求的区间没有交集 if (i > e || j < b) return -1; if (b >= i && e <= j) return M[node]; p1 = query(2 * node, b, (b + e) / 2, M, A, i, j); p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j); //return the position where the overall //minimum is if (p1 == -1) return M[node] = p2; if (p2 == -1) return M[node] = p1; if (A[p1] <= A[p2]) return M[node] = p1; return M[node] = p2; } int main() { int M[MAXIND]; //下标1起才有意义,否则不是二叉树,保存下标编号节点对应区间最小值的下标. memset(M,-1,sizeof(M)); int a[]={3,4,5,7,2,1,0,3,4,5}; build(1, 0, sizeof(a)/sizeof(a[0])-1, M, a); cout<<query(1, 0, sizeof(a)/sizeof(a[0])-1, M, a, 0, 9)<<endl; return 0; } //求区间最小值（区间更新+延迟标记） #include<stdio.h> #define MAX 65535 #define INFINITY 65535 #define min(a,b) a<b?a:b struct node { int val; int addmark; //延迟标记 }segtree[MAX]; void buildtree(int root,int start ,int end,int a[]) //建树 { segtree[root].addmark=0; if(start==end) segtree[root].val=a[start]; else { buildtree(root*2+1,start,(start+end)/2,a);//创建左子树 buildtree(root*2+2,(start+end)/2+1,end,a);//创建右子树 segtree[root].val=min(segtree[root*2+1].val,segtree[root*2+2].val); //更新节点的值 } } //root : 当前线段树根节点下标 void pushdown(int root)//向下传递 { if(segtree[root].addmark!=0) { segtree[root*2+1].addmark+=segtree[root].addmark;// 多次延迟标记且没有向下传递 segtree[root*2+2].addmark+=segtree[root].addmark; segtree[root*2+1].val+=segtree[root].addmark;//区间最小值也需要加上这个addmark segtree[root*2+2].val+=segtree[root].addmark; segtree[root].addmark=0;//传递完成，标记清空 } } //[qstart,qend] 需要查询的区间 int query(int root,int start,int end,int qstart,int qend) { if(qstart>end||qend<start)//没有交集 return INFINITY; if(qstart<=start&&qend>=end)//包含当前区间 return segtree[root].val; pushdown(root);//延迟标记向下传递 int mid=(start+end)/2; return min(query(root*2+1,start,mid,qstart,qend),query(root*2+2,mid+1,end,qstart,qend)); //查询左右子树并返回最小值 } //[cstart,cend] 需要update的区间 void update(int root,int start,int end,int cstart,int cend,int addval) { if(cstart>end||cend<start)//区间没有交集 return ; if(start>=cstart&&end<=cend)//包含当前区间 { segtree[root].addmark+=addval; segtree[root].val+=addval;//更新得值 return ; } pushdown(root);//延迟标记向下传递 int mid=(start+end)/2; update(root*2+1,start,mid,cstart,cend,addval);//更新左子树 update(root*2+2,mid+1,end,cstart,cend,addval);//更新有子树 segtree[root].val=min(segtree[root*2+1].val,segtree[root*2+2].val); //返回更新后节点最小值 } int main() { int a[]={3,4,5,7,2,1,0,3,4,5}; buildtree(1,0,9,a); int t=query(1,0,9,0,6);//查询【0,6】 printf("%d\n",t); update(1,0,9,4,6,2);//更新【4,6】 int tt=query(1,0,9,0,6);//查询【0,6】 printf("%d\n",tt); return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-669882.html

    技术

    最新回复(0)