权威的网站建设公司,建筑外观设计网站,wordpress的页面和首页一样,asp网站安全性引入#xff1a;RMQ问题#xff1a;
什么是RMQ#xff1f; 显然#xff0c;我们无法用前缀维护#xff0c;因此#xff0c;我们需要用到线段树的知识#xff1a;
什么是线段树#xff1f;
线段树是用一种树状结构存储一个连续区间信息的数据结构
下面我们用图解释用…引入RMQ问题
什么是RMQ 显然我们无法用前缀维护因此我们需要用到线段树的知识
什么是线段树
线段树是用一种树状结构存储一个连续区间信息的数据结构
下面我们用图解释用它来查询2--5信息的方式 由此我们可以得到几点性质
1.他是一个平衡的二叉树。
2.对于任意两个节点要么完全包含要么互不相交。
3.任意的线段[a,b]在查询过程中最多分为log(b-a)个。
4.除建树外为logn.
我们来一道模板题试试水 下面是AC代码
#includebits/stdc.h
using namespace std;
int n,a[100000];
int tree[4*100000];
void build(int p,int l,int r){if(lr){tree[p]a[l];return;}int mid(lr)/2;build(p*2,l,mid);build(p*21,mid1,r);tree[p]tree[p*21]tree[p*2];return;
}
void change(int p,int l,int r,int pos,int num){if(lr){tree[p]num;return;}int mid(lr)/2;if(posmid) change(p*2,l,mid,pos,num);else change(p*21,mid1,r,pos,num);tree[p]tree[2*p]tree[2*p1];return;
}
int calc(int p,int l,int r,int x,int y){if(lxry){return tree[p];}int mid(lr)/2;if(ymid) return calc(p*2,l,mid,x,y);if(xmid) return calc(p*21,mid1,r,x,y);return calc(p*2,l,mid,x,mid)calc(p*21,mid1,r,mid1,y);
}
int main(){cinn;for(int i1;in;i) cina[i];build(1,1,n);for(int i1;in;i){int x,y,z;cinxyz;if(x1){change(1,1,n,y,z);}else coutcalc(1,1,n,y,z);}
}
让我们来看看它的实际应用吧
区间和问题之懒标记 我们维护一下节点的两个信息
1.sum[i]第i个节点对应的区间和。
2.add[i]第i个节点对应区间整体加上的值并且没有同步给儿子。
这里我们就知道了为什么叫lazy,该标记仅当被标记的区间有部分被更改才顺路把标记下放给它的儿子。这样就可以减少修改的次数了。
下面是AC代码
#includebits/stdc.h
using namespace std;
#define int long long
int n,a[100010],m;
int tree[4*100010];
int lazy[4*100010];
void build(int p,int l,int r){//建树 if(lr){tree[p]a[l];return;}int mid(lr)/2;build(p*2,l,mid);build(p*21,mid1,r);tree[p]tree[p*21]tree[p*2];return;
}
void pushdown(int p,int l,int r){//lazy标记下移 int mid(lr)/2;lazy[p*2]lazy[p];lazy[p*21]lazy[p];tree[p*2]lazy[p]*(mid-l1);//更新子节点的值 tree[p*21]lazy[p]*(r-mid);lazy[p]0;//自己因为下移清0
}
void change(int p,int l,int r,int x,int y,int num){if(xlry){tree[p]num*(r-l1);lazy[p]num;return;}if(lazy[p]!0){//区间部分修改需要下移 pushdown(p,l,r);}int mid(lr)/2;if(ymid) change(p*2,l,mid,x,y,num);if(xmid) change(p*21,mid1,r,x,y,num);if(xmidymid){change(p*2,l,mid,x,mid,num);change(p*21,mid1,r,mid1,y,num);}tree[p]tree[2*p]tree[2*p1];return;
}
int calc(int p,int l,int r,int x,int y){if(lxry){return tree[p];}if(lazy[p]!0){pushdown(p,l,r);}int mid(lr)/2;if(ymid) return calc(p*2,l,mid,x,y);if(xmid) return calc(p*21,mid1,r,x,y);return calc(p*2,l,mid,x,mid)calc(p*21,mid1,r,mid1,y);
}
signed main(){cinnm;for(int i1;in;i) scanf(%lld,a[i]);build(1,1,n);for(int i1;im;i){int x,y,k,op;scanf(%lld%lld%lld,op,x,y);if(op1){scanf(%lld,k);change(1,1,n,x,y,k);}else coutcalc(1,1,n,x,y)endl;}
}
区间平方和问题 我们还是用lazy标记不过这时我们维护的sum应该是平方和。那么我们如何维护呢 因此我们只要维护ai的前缀和即可。
下面是AC代码
#includebits/stdc.h
using namespace std;
#define int long long
int n,a[100010],m,sum[4*100010];
int tree[4*100010];
int lazy[4*100010];
void pushdown(int p,int l,int r);
int calc(int p,int l,int r,int x,int y,int k);
void build(int p,int l,int r){//建树 if(lr){tree[p]a[l]*a[l];sum[p]a[l];return;}int mid(lr)/2;build(p*2,l,mid);build(p*21,mid1,r);tree[p]tree[p*21]tree[p*2];sum[p]sum[p*21]sum[p*21];return;
}
void pushdown(int p,int l,int r){//lazy标记下移 int mid(lr)/2;lazy[p*2]lazy[p];lazy[p*21]lazy[p];tree[p*2]2*lazy[p]*(sum[2*p])lazy[p]*lazy[p]*(mid-l1);//更新子节点的值 tree[p*21]2*lazy[p]*(sum[2*p1])lazy[p]*lazy[p]*(r-mid);sum[p*2]lazy[p]*(mid-l1);sum[p*21]lazy[p]*(r-mid);lazy[p]0;//自己因为下移清0
}
void change(int p,int l,int r,int x,int y,int num){if(xlry){tree[p]2*num*(sum[p])num*num*(r-l1);sum[p]num*(r-l1);lazy[p]num;return;}if(lazy[p]!0){//区间部分修改需要下移 pushdown(p,l,r);}int mid(lr)/2;if(ymid) change(p*2,l,mid,x,y,num);if(xmid) change(p*21,mid1,r,x,y,num);if(xmidymid){change(p*2,l,mid,x,mid,num);change(p*21,mid1,r,mid1,y,num);}tree[p]tree[2*p]tree[2*p1];sum[p]sum[2*p]sum[2*p1];return;
}
int calc(int p,int l,int r,int x,int y,int k){if(lxry){if(k1) return tree[p];else return sum[p];}if(lazy[p]!0){pushdown(p,l,r);}int mid(lr)/2;if(ymid) return calc(p*2,l,mid,x,y,k);if(xmid) return calc(p*21,mid1,r,x,y,k);return calc(p*2,l,mid,x,mid,k)calc(p*21,mid1,r,mid1,y,k);
}
signed main(){cinnm;for(int i1;in;i) scanf(%lld,a[i]);build(1,1,n);for(int i1;im;i){int x,y,k,op;scanf(%lld%lld%lld,op,x,y);if(op1){scanf(%lld,k);change(1,1,n,x,y,k);}else coutcalc(1,1,n,x,y,1)endl;}
}
