//結構體數組建樹,求區間最小值,單點更新最小值
#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;
}