做项目搭建网站 构建数据库,毕业设计做健身房网站的意义,中小学图书馆网站建设,杭州专业网站排名优化目录
分块
分块算法步骤#xff1a;
树状数组
树状数组步骤#xff1a;
线段树点更新
点更新步骤#xff1a;
线段树区间更新
区间更新步骤#xff1a; 不同于倍增和前缀和与差分序列。
前缀和处理不更新的区间和
差分处理离线的区间更新问题
倍增处理离线的区间…目录
分块
分块算法步骤
树状数组
树状数组步骤
线段树点更新
点更新步骤
线段树区间更新
区间更新步骤 不同于倍增和前缀和与差分序列。
前缀和处理不更新的区间和
差分处理离线的区间更新问题
倍增处理离线的区间最值问题
分块树状数组线段树
分块处理求多次区间更新的区间和在线算法
树状数组求多次点更新的区间和 (在线算法)
线段树求多次点更新或区间更新的区间最值 在线算法 分块
分块算法思想基于优化后的暴力。
分块的本质就是维护每个块的suf数组(和lz)然后分整个块处理和非整个块暴力处理
分块操作是修改原数组及懒标维护suf 题目POJ 3648 一个简单的整数问题 分块算法步骤 1预处理块build初始化每块的左右下标L[],和R[]每个下标的所属块号be每块的和suf 2区间修改update对于完整的块仅修改懒标lz不完整的就暴力修改a和suf 3区间查询query 对于完整的块直接利用懒标lz和suf不完整的就暴力a和lz 这里没有什么懒标下放这又不是求区间max
#include bits/stdc.h//POJ3648
using namespace std;
const int N100010;
typedef long long ll;
ll suf[N],lz[N];//分块的本质是维护每个块的suf数组(和lz)然后分整个块处理和非整个块暴力处理相当于优化后的暴力
int a[N],L[N],R[N],be[N];
int n,m;
//分块:我们处理下标都是从1开始
void build(){//L[]R[]每块的左右下标be[]每个下标的所属块号suf[]每块的和int tsqrt(n);int numn/t;if(n%t) num;//t是块长num是块数for(int i1;inum;i){L[i](i-1)*t1; R[i]i*t;}R[num]n;//更改最后一块的右下标for(int i1;inum;i)for(int jL[i];jR[i];j){be[j]i;suf[i]a[j];//初始化每点的be和每块的suf}
}
//区间修改
void update (int l,int r,int d){//完整块就修改懒标lz不完整就修改asufint pbe[l],qbe[r];if(pq){//如果在同一块就暴力修改a和suffor(int il;ir;i) a[i]d;suf[p]d*(r-l1);}else{//否则完整的块修改懒标lz不完整还是暴力a和suffor(int ip1;iq-1;i) lz[i]d;for(int il;iR[p];i) a[i]d;suf[p]d*(R[p]-l1);for(int iL[q];ir;i) a[i]d;suf[q]d*(r-L[q]1);}
}ll query(int l,int r){//完整块suf和lz不完整就a和lzint pbe[l],qbe[r];ll ans0;if(pq){//同一块就看a和lzfor(int il;ir;i) ansa[i];anslz[p]*(r-l1);}else{//否则完整就suflz不完整还是a和lzfor(int ip1;iq-1;i) anssuf[i]lz[i]*(R[i]-L[i]1);for(int il;iR[p];i) ansa[i];for(int iL[q];ir;i) ansa[i];anslz[q]*(r-L[q]1);}return ans;
}int main(){cinnm;int l,r,d;char op[3];//不要输入字符输入字符串for(int i1;in;i){scanf(%lld,a[i]);}build();for(int i1;im;i){scanf(%s %d %d,op,l,r);if(op[0]C){scanf(%d,d);update(l,r,d);}else{printf(%lld\n,query(l,r));}}
}树状数组
树状数组思想和原数组一一对应且是通过“二进制 ”分解维护区间
树状数组本质就是创建了一个离散的一维数组c每个点维护不同区间的前缀和。更新和查询都是离散的
树状数组操作是修改c数组的后继查询c数组的前驱 c[i]区间维护长度 i末尾有连续的k个0则c[i]保存的区间长度为2^k即从a[i]向前的2^k个元素 树状数组步骤 单点修改更新add找后继 更新该元素所有的祖先节点 查询前缀和sum找前驱 加上左侧所有子树的根也就是自己的前兄弟故称为前驱 #include bits/stdc.h//一维树状数组 性能是log(n)
using namespace std;
typedef long long ll;
const int maxn10000;
ll c[maxn];//c[]为树状数组
int n,a[maxn];
int lowbit(int i){ return (-i)i;}
//获取c[i]区间的长度(计算机中的负数是以补码来存的)
void add(int i,int z){ for(;in;ilowbit(i)) c[i]z;}
//c[i]的后继都加上z直接后继为[ilowbit(i)]
ll sum(int i){//求前缀和a[1]~a[i]把i前面所有的根加上即可直接前驱为[i-lowbit(i)]ll s0;for(;i0;i-lowbit(i)) sc[i];return s;
}ll sum(int i,int j){ return sum(j)-sum(i-1);}//求区间和int main(){cinn;for(int i1;in;i){//数组必须从1开始输入cina[i];add(i,a[i]);//点更新更新树状数组} int x1,x2;cinx1;coutsum(x1)\n;cinx1x2;coutsum(x1,x2);return 0;
}
那么仅仅把sum改成从(1,1)到(x,y)求和即可变成二维的树状数组
#include bits/stdc.h//二维树状数组
using namespace std;
typedef long long ll;
const int maxn10000;
ll c[maxn][maxn];
int n,a[maxn][maxn];int lowbit(int i){ return (-i)i;}void add(int x,int y,int z){for(int ix;in;ilowbit(i))for(int jy;jn;jlowbit(j)){c[i][j]z;}
}ll sum(int x,int y){//求(1,1)到(x,y)和ll s0;for(int ix;i0;i-lowbit(i))for(int jy;j0;j-lowbit(j)){sc[i][j];}return s;
}ll sum(int x1,int y1,int x2,int y2){return sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)sum(x1-1,y1-1);
}int main(){cinn;for(int i1;in;i)for(int j1;jn;j){cina[i][j];add(i,j,a[i][j]);}int x1,y1,x2,y2;cinx1y1;coutsum(x1,y1)\n;cinx1y1x2y2;coutsum(x1,y1,x2,y2);} 线段树点更新
线段树思想建立一颗二叉树来用每个节点去维护对应区间的信息
线段树的本质是在4maxn大小的一维树形离散数组tree(节点)上存储区间的信息。建立更新和查询也都是离散的
线段树操作是找到并修改叶节点信息来维护整棵树查询是找所有的对应节点 要注意
我们建立的二叉树在非叶子层时都是满二叉树。所以k节点的左孩子一定是2k右孩子一定是2k1另外k(节点)的值和l,r的值没有任何关系只不过是lr时候k是叶子节点 下图是初始化线段树的节点号 但是整棵树一定是按照dfs序来更新的也因此叶子节点也是dfs序更新的 点更新步骤 build初始化节点信息找到叶节点放置数组信息然后上传到所有节点更新信息 update找到对应的点将i下标的值更新为v query: 找到对正确的节点就返回否则就继续分叉找 千万别看代码多长基本就函数中最前面的几句有用剩余操作的都是在找孩子进行递归。
#include bits/stdc.h
using namespace std;
const int maxn100005,INF0x3f3f3f3f;
int n,a[maxn];
struct node{ int l,r,mx;}tree[maxn*4];//存放左右端点l,rmx为区间最值tree存放树节点号void build(int k,int l,int r){//创建线段树初始化每个节点tree[k].ll;tree[k].rr;if(lr){tree[k].mxa[l];return ;}int mid(lr)/2;build(k1,l,mid);//建树时候范围一定要变化build(k1|1,mid1,r);tree[k].mxmax(tree[k1].mx,tree[k1|1].mx);//创建完成孩子后再更新最大值
}void update(int k,int i,int v){//单点修改在k节点将i下标的值更新为vif(tree[k].ltree[k].rtree[k].li){//找i下标的叶子更新tree[k].mxv;return ;}int mid(tree[k].ltree[k].r)/2;if(imid) update(k1,i,v);//否则就进入左子树lc或右子树更新rcelse update(k1|1,i,v);tree[k].mxmax(tree[k1].mx,tree[k1|1].mx);//孩子更新完后修改最大值
}int query(int k,int l,int r){//区间查询找到对正确的节点就返回否则就继续分叉找if(tree[k].lltree[k].rr){return tree[k].mx;//找到了}int mid(tree[k].ltree[k].r)/2;int maxx-INF;if(lmid){//否则就找左子树或右子树的最值maxxmax(maxx,query(k1,l,r));}if(rmid){maxxmax(maxx,query(k1|1,l,r));}return maxx;
}void print(int k){if(tree[k].mx){coutk\ttree[k].l\ttree[k].r\ttree[k].mx\t\n;print(k1);print((k1)1);}
}int main(){int l,r,i,v;cinn;for(int i1;in;i) cina[i];build(1,1,n);//创建二叉线段树为啥传入树根呢答方便找左右孩子print(1);cinlr;coutquery(1,l,r)\n;//查询区间最值ciniv;update(1,i,v);//点更新print(1);cinlr;coutquery(1,l,r)\n;
}
输入样例后建立的二叉树 线段树区间更新 区间更新步骤 创建线段树初始化节点信息找到叶节点放置数组信息然后上传到所有节点更新信息 区间修改在k节点上修改[l,r]区间为v值整体包含就做懒标否则就继续分叉分叉前一定要懒标下移 区间查询找到对正确的节点就返回否则就继续分叉找分叉前一定要懒标下移 也就是相对点更新来讲多了懒标的处理
#include bits/stdc.h
using namespace std;
const int maxn100005,INF0x3f3f3f3f;
int n,a[maxn];
struct node{ int l,r,mx,lz;}tree[maxn*4];//存放左右端点l,rmx表示区间[l,r]最值lz表示懒标 tree存放树节点号
//二叉树的本质是在4k的一维dfs序的树形离散数组(节点)上存储的信息。另外k(节点)的值和l,r的值没有任何关系只不过是lr时候k是叶子节点
void lazy(int k,int v){tree[k].mxtree[k].lzv;}//给节点k打懒标void pushdown(int k){//从k节点下传懒标传给子树只会传一次否则就退化成单点修改了lazy(k1,tree[k].lz);lazy(k1|1,tree[k].lz);//的优先级太高了tree[k].lz-1;//清除当前节点懒标
}void build(int k,int l,int r){//创建线段树创建二叉树然后在叶节点放置数组信息然后上传到所有节点更新信息tree[k].ll;tree[k].rr;tree[k].lz-1;//初始化节点if(lr){tree[k].mxa[l];return ;//按dfs顺序更新叶子}int mid(lr)/2;build(k1,l,mid);//建树时候范围一定要变化build(k1|1,mid1,r);//左右孩子节点为2k和2k1分别维护[l,mid]和[mid1,r]的区间信息tree[k].mxmax(tree[k1].mx,tree[k1|1].mx);//更新最大值
}void update(int k,int l,int r,int v){//区间修改在k节点上修改[l,r]区间为v值整体包含就做懒标否则就继续分叉if(tree[k].lltree[k].rr){//恰好找到区间覆盖也行return lazy(k,v);//直接做懒标记并结束本层这个return不是返回值的}if(tree[k].lz!-1) pushdown(k);//有懒标先下移再进入子树这样下个节点的lz和mx就更新了int mid(tree[k].ltree[k].r)/2;if(lmid) update(k1,l,r,v);//传节点即可因为我们用的是节点的信息(build时是l到mid区间为左子树所以必须lmid)if(rmid) update(k1|1,l,r,v);tree[k].mxmax(tree[k1].mx,tree[k1|1].mx);//更新最大值
}int query(int k,int l,int r){//区间查询找到对正确的节点就返回否则就继续分叉找if(tree[k].lltree[k].rr){//找到就返回return tree[k].mx;}if(tree[k].lz!-1) pushdown(k);//有懒标先下移再进入子树int mid (tree[k].ltree[k].r)/2;int maxx-INF;if(lmid) maxxmax(maxx,query(k1,l,r));//否则就找左子树或右子树的最值if(rmid) maxxmax(maxx,query(k1|1,l,r));return maxx;
}void print(int k){if(tree[k].mx){//从根开始dfs顺序访问每个节点123 ……coutk\ttree[k].l\ttree[k].r\ttree[k].mx\t\n;print(k1);print(k1|1);}
}int main(){int l,r,v;cinn;for(int i1;in;i) cina[i];build(1,1,n);//创建线段树 print(1);cinlr;coutquery(1,l,r)\n;//区间查询cinlrv;update(1,l,r,v);//区间修改print(1);for(int i1;in;i)couta[i] ;cout\n;while(l){cinlr;coutquery(1,l,r)\n;}
}
