门户网站建设自查整改报告,哈尔滨做网站的,未央区建设局网站,网站建设规划结构前言
昨天某B组讲主席树#xff0c;然后就作死的去听了#xff0c;也没听懂#xff08;因为连线段树都不懂#xff09;#xff0c;然后好奇心就去问了一下老师线段树是个蛤#xff0c;然后这篇博客就诞生了。
正题
首先线段树就是一个可以快速区间改变和询问的东东然后就作死的去听了也没听懂因为连线段树都不懂然后好奇心就去问了一下老师线段树是个蛤然后这篇博客就诞生了。
正题
首先线段树就是一个可以快速区间改变和询问的东东实现方法就是用树啦。具体方法看下面。 首先我们讲一下例题
最大值jzoj1959
一串序列有2种操作 1.询问一个区间内的最大值 2.改变一个数的值 这道题明显没有用到区间改值那这里先不扯区间改值 以下线段树草图 每个点表示的是一个区间内的树 建树代码
int build(int l,int r,int k)
{if (lr) return tree[k].wa[l];//如果只有一个数就直接返回int wz(lr)/2;//中间位置return tree[k].wmax(build(l,wz,2*k),build(wz1,r,2*k1));//分叉
}
然后是查找某区间 草图 分成多份寻找需要的区间 查找代码
void find(int l,int r,int x,int y,int k)//表示在l~r之间需要x~y的最大值
{if (xl yr) {ansmax(ans,tree[k].w);return;}int wz(lr)/2;//中心if (ywz) find(l,wz,x,y,2*k);//需要全包涵在左边else if (xwz) find(wz1,r,x,y,2*k1);//需要全包涵在右边else {find(l,wz,x,wz,2*k);find(wz1,r,wz1,y,2*k1);//有左也有右}return;
}
然后由于这道题只需要改变单个数的瞎水水就过了 代码
#includecstdio
#includeiostream
using namespace std;
struct point{int w,lazy;
}tree[400014];
int n,m,w,x,y,a[100007],ans;
int build(int l,int r,int k)//建数
{if (lr) return tree[k].wa[l];int wz(lr)/2;return tree[k].wmax(build(l,wz,2*k),build(wz1,r,2*k1));
}
void find(int l,int r,int x,int y,int k)//查找
{if (xl yr) {ansmax(ans,tree[k].w);return;}int wz(lr)/2;if (ywz) find(l,wz,x,y,2*k);else if (xwz) find(wz1,r,x,y,2*k1);else {find(l,wz,x,wz,2*k);find(wz1,r,wz1,y,2*k1);}return;
}
void updata(int l,int r,int x,int y,int k)//改变
{if (lx rx) {tree[k].wy;return;}//改变并返回int wz(lr)/2;//确定位置if (xwz) updata(l,wz,x,y,2*k);//在左边else if (xwz) updata(wz1,r,x,y,2*k1);//在右边tree[k].wmax(tree[2*k].w,tree[2*k1].w);//更新值
}
int main()
{scanf(%d,n);for (int i1;in;i) scanf(%d,a[i]);build(1,n,1);//建树scanf(%d,m);for (int i1;im;i){scanf(%d,w);if (w2){scanf(%d%d,x,y);ans0;find(1,n,x,y,1);//查找printf(%d\n,ans);}else if (w1){scanf(%d%d,x,y);updata(1,n,x,y,1);//改变}}
} 最大值2jzoj1960
依旧是一个序列两种操作 1.询问一个区间内的值 2.让一个区间内的值加上一个数可能是负数 这里就需要用到区间改变了 像查找一样找到区间如果直接改变整棵子树会超时所以先标记查找时在下传 好了区间改变代码
void updata(int l,int r,int x,int y,int num,int k)
{if (lx ry) {tree[k].lazynum;//标记tree[k].wnum;//改变自己return;}if (tree[k].lazy!0)//顺便下传{tree[k*2].wtree[k].lazy;tree[k*2].lazytree[k].lazy;tree[k*21].wtree[k].lazy;tree[k*21].lazytree[k].lazy; tree[k].lazy0;}int wz(lr)/2;//中心if (ywz) updata(l,wz,x,y,num,2*k);else if (xwz) updata(wz1,r,x,y,num,2*k1);else {updata(l,wz,x,wz,num,2*k);updata(wz1,r,wz1,y,num,2*k1);}tree[k].wmax(tree[2*k].w,tree[2*k1].w);//更新
}
代码
#includecstdio
#includeiostream
using namespace std;
struct point{long long w,lazy;
}tree[400030];
long long ans;
int n,m,w,x,y,a[100007],num;
int build(int l,int r,int k)//建树
{if (lr) return tree[k].wa[l];int wz(lr)/2;return tree[k].wmax(build(l,wz,2*k),build(wz1,r,2*k1));
}
void find(int l,int r,int x,int y,int k)//查找
{if (xl yr) {ansmax(ans,tree[k].w);return;}if (tree[k].lazy!0){tree[k*2].wtree[k].lazy;tree[k*2].lazytree[k].lazy;tree[k*21].wtree[k].lazy;tree[k*21].lazytree[k].lazy; tree[k].lazy0;}int wz(lr)/2;if (ywz) find(l,wz,x,y,2*k);else if (xwz) find(wz1,r,x,y,2*k1);else {find(l,wz,x,wz,2*k);find(wz1,r,wz1,y,2*k1);}
}
void updata(int l,int r,int x,int y,int num,int k)//改值
{if (lx ry) {tree[k].lazynum;tree[k].wnum;return;}if (tree[k].lazy!0){tree[k*2].wtree[k].lazy;tree[k*2].lazytree[k].lazy;tree[k*21].wtree[k].lazy;tree[k*21].lazytree[k].lazy; tree[k].lazy0;}int wz(lr)/2;if (ywz) updata(l,wz,x,y,num,2*k);else if (xwz) updata(wz1,r,x,y,num,2*k1);else {updata(l,wz,x,wz,num,2*k);updata(wz1,r,wz1,y,num,2*k1);}tree[k].wmax(tree[2*k].w,tree[2*k1].w);
}
int main()
{scanf(%d,n);for (int i1;in;i) scanf(%d,a[i]);build(1,n,1);scanf(%d,m);for (int i1;im;i){scanf(%d,w);if (w2){scanf(%d%d,x,y);//查找ans-2147483647;find(1,n,x,y,1);printf(%lld\n,ans);}else if (w1){scanf(%d%d%d,x,y,num);//改值updata(1,n,x,y,num,1);}}
}
