上海工厂网站建设,深圳比较好的vi设计公司,虚拟主机子网站,wordpress过滤html标签了线段树的应用范围非常广#xff0c;可以处理很多与区间有关的题目。 将区间抽象成一个节点#xff0c;在这个节点中储存这个区间的一些值#xff0c;那么如果看成节点的话#xff0c;这就很像一棵满二叉树#xff0c;所以我们可以用一维数组来储存节点。那么就要考虑父子节…线段树的应用范围非常广可以处理很多与区间有关的题目。 将区间抽象成一个节点在这个节点中储存这个区间的一些值那么如果看成节点的话这就很像一棵满二叉树所以我们可以用一维数组来储存节点。那么就要考虑父子节点之间的关系。 如果一个一个节点的下标是x 那么父节点就是x/2 左子节点就是2x(可以写为x1),右子节点就是2x1(可以写为x11) 那么我们就可以实现节点之间的转移操作实际上相互影响的也只有父子节点之间相互影响所以在更新的时候有两种更新方式一种是用子节点来更新父节点(pushup)一种是用父节点来更新子节点(pushdown)。
还有一个问题就是这个一维数组该开多大假设区间大小为n那么我们就将数组开到4n大小。
既然用线段树那么肯定要定义结构体来表示每个点结构体的定义首先要有l,r来表示区间范围然后需要维护的值肯定要放入结构体中至于其他的变量就要根据维护值是否能用子节点算出父节点来决定如果不能的话那么就要考虑引入新的变量。
线段树看起来似乎很高深但是实际上只有几个函数模板比较固定 build()//初始化线段树 modify()//修改 pushup()//用子节点更新父节点 pushdown()//将父节点的更新传到子节点 query() //查询操作 对于这些操作我们还是结合具体的例题来分析。
1275. 最大数活动 - AcWing 题目稍微翻译一下就是向一个空数组中插入数在插入的同时进行局部区间最大值的访问。用上线段树后思路也没什么复杂的我们可以先将整个数组先用线段树维护起来空位置对应的区间就是0那么我向末尾插入数的时候实际上也就相当于对区间进行单点修改单点修改的话实际上容易想到树状数组但是树状数组用到了前缀和的原理前缀和是没办法解决最大值问题的所以这里还是要用线段树来实现。
我们先来确定结构体如何确定首先得有l,r来表示区间然后max也必须定义在结构体中然后判断是否能用子节点的值来更新父节点显然是可以的父区间的最大值max(左子区间的最大值右子区间的最大值)。
#includebits/stdc.h
using namespace std;
const int N200010;
struct node
{int l,r,mx;
}tr[4*N];
int m,p;
void build(int u,int l,int r)
{tr[u]{l,r};if(lr) return;int midlr1;build(u1,l,mid),build(u1|1,mid1,r);}
void pushup(int u)
{tr[u].mxmax(tr[u1].mx,tr[u1|1].mx);
}
void modify(int u,int x,int c)
{if(tr[u].lxtr[u].rx) tr[u].mxc;else{int midtr[u].ltr[u].r1;if(xmid) modify(u1,x,c);else modify(u1|1,x,c);pushup(u);}
}
int query(int u,int l,int r)
{if(tr[u].lltr[u].rr) return tr[u].mx;int midtr[u].ltr[u].r1;if(lmid) return query(u1|1,l,r);else if(rmid) return query(u1,l,r);else return max(query(u1,l,r),query(u1|1,l,r));
}
int main()
{int last0,n0;scanf(%d%d,m,p);build(1,1,m);while(m--){char op[2];int a;scanf(%s%d,op,a);if(op[0]A){a((long long)lasta)%p;modify(1,n,a);}else {lastquery(1,n-a1,n);coutlastendl;}}
}
ps:修改单点的话就不用pushdown操作了pushdown需要用到懒标记有些麻烦能不用当然更好。
245. 你能回答这些问题吗245. 你能回答这些问题吗 - AcWing题库 这里是单点修改很容易想到用树状数组来实现但是树状数组只能维护类似于前缀和这种一整个区间的东西而我们查询区间中的连续最大子段和显然用树状数组就没办法实现那么如果用线段树的话又该怎么实现呢还是先来看如何定义结构体显然我们需要储存最大连续子段和但是这样够不够呢显然是不够的因为子节点无法更新父节点虽然父区间的最大值有可能是左右子区间中的一段但是还有可能是跨区间的如果是跨区间的话要想更新就需要用到左区间的最大后缀和右区间的最大前缀那么现在就要多维护两个变量——最长前缀和最长后缀那么现在考虑最长前缀和最长后缀能否能通过子节点来更新父节点显然是不可以以最长前缀为例要用子节点计算的话有两种情况一种就是左子节点的最长前缀一种是左区间加右区间的最大前缀。所以我们实际上还是要维持一个区间和那么区间和可以由子区间更新父区间吗当然可以。至此便不用再加别的变量就可以实现这个问题了。
#includebits/stdc.h
using namespace std;
const int N500010;
int n,m;
int a[N];
struct node{int l,r,mx,lmx,rmx,sum;
}tr[4*N];
void pushup(node u,node l,node r)
{u.mxmax(max(l.mx,r.mx),l.rmxr.lmx);u.lmxmax(l.lmx,l.sumr.lmx);u.rmxmax(r.rmx,r.suml.rmx);u.suml.sumr.sum;
}
void pushup(int u)
{pushup(tr[u],tr[u1],tr[u1|1]);
}
void build(int u,int l,int r)
{if(lr) tr[u]{l,r,a[l],a[l],a[l],a[l]};else{tr[u]{l,r};int midlr1;build(u1,l,mid),build(u1|1,mid1,r);pushup(u);}
}
void modify(int u,int x,int v)
{if(tr[u].lxtr[u].rx) tr[u]{x,x,v,v,v,v};else{int midtr[u].ltr[u].r1;if(xmid) modify(u1,x,v);else modify(u1|1,x,v);pushup(u);}
}
node query(int u,int l,int r)
{if(ltr[u].ltr[u].rr) return tr[u];int midtr[u].ltr[u].r1;if(lmid) return query(u1|1,l,r);else if(rmid) return query(u1,l,r);else{auto leftquery(u1,l,r),rightquery(u1|1,l,r);node res;pushup(res,left,right);return res;}
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,a[i]);build(1,1,n);while(m--){int op,a,b;scanf(%d%d%d,op,a,b);if(op1)//最大子段和{if(ab)swap(a,b);coutquery(1,a,b).mxendl;}else//将a[x]改成y{modify(1,a,b);}}
}
246. 区间最大公约数246. 区间最大公约数 - AcWing题库 这里虽然需要修改最大区间但是修改操作是将区间整体加上一个数这里可以用差分来处理一下进而避免区间修改操作毕竟区间修改还怪麻烦的那么具体该怎么实现呢维护差分是很容易的问题在于如何维护gcd的值这里需要用到欧几里得算法,我们简单证明一下 gcd(a1,a2,a3,...,an)gcd(a1,a2-a1,a3-a2,...) 令ggcd(a1,a2,a3...); 那么a1%g0,a2%g0,a3%g0,... 故而(a2-a1)%g0,(a3-a2)%g0,... 故而gcd(a1,a1-a2,a2-a3,...)ggcd(a1,a2-a1,a3-a2,...)是最大公因数g是一个因数所以满足大于等于的关系 令ggcd(a1,a2-a1,a3-a2,...), 那么a1%g0,(a2-a1)%g0,所以a2%g0,以此类推a3%g0,... 故而gcd(a1,a2,a3,...,an)g 所以gcd(a1,a2,a3,...,an)gcd(a1,a2-a1,a3-a2,...) 差分数组是什么呢 b1a1-a0 b2a2-a1 ... 所以我们可以通过维护差分数组来实现。 然后如果需要获得gcd需要维护哪些值呢gcd(sum(1~bl),gcd(b[l1],...,b[r])) 区间和这个很容易得到那么后面的gcd(b[l1],...,b[r])怎么得到呢显然如果维和子区间的gcd的话可以用子区间的gcd得到父区间的gcd所以就只需要维护区间的gcd和sum即可。
#includebits/stdc.h
using namespace std;
typedef long long ll;
const int N500010;
int n,m;
long long a[N];
struct node{int l,r;ll sum,g;
}tr[4*N];
ll gcd(ll a,ll b)
{return b?gcd(b,a%b):a;
}
void pushup(node u,node l,node r)
{u.suml.sumr.sum;u.ggcd(l.g,r.g);
}
void pushup(int u)
{pushup(tr[u],tr[u1],tr[u1|1]);
}
void build(int u,int l,int r)
{if(lr) {ll ba[r]-a[r-1];tr[u]{l,r,b,b};}else{tr[u].ll,tr[u].rr;int midlr1;build(u1,l,mid),build(u1|1,mid1,r);pushup(u);}
}
void modify(int u,int x,ll v)
{if(tr[u].lxtr[u].rx) {ll btr[u].sumv;tr[u]{x,x,b,b};}else{int midtr[u].ltr[u].r1;if(xmid) modify(u1,x,v);else modify(u1|1,x,v);pushup(u);}
}node query(int u,int l,int r)
{if(ltr[u].ltr[u].rr) return tr[u];int midtr[u].ltr[u].r1;if(lmid) return query(u1|1,l,r);else if(rmid) return query(u1,l,r);//一定要记得写returnelse{auto leftquery(u1,l,r),rightquery(u1|1,l,r);node res;pushup(res,left,right);return res;}
}int main()
{scanf(%d%d,n,m);a[0]0;for(int i1;in;i) scanf(%lld,a[i]);build(1,1,n);while(m--){char op[2];int l,r;scanf(%s%d%d,op,l,r);if(op[0]Q){auto left query(1, 1, l);node right({0,0,0,0});if(l1r) rightquery(1,l1,r);coutabs( gcd(left.sum,right.g) )endl;}else{long long v;scanf(%lld,v);modify(1,l,v);if(r1n)modify(1,r1,-v);}}
}
243. 一个简单的整数问题2活动 - AcWing 这里是给一段区间同时加上一个数也很容易想到能不能用差分代替区间修改但是我们如果用线段树维护差分数组的话没有办法快速获得区间和所以这里无可避免的需要实现区间修改那么就要用到pushdown操作了。
pushdown的操作虽然麻烦但实际上思路还是比较容易的。 我们在定义区间节点的时候实际上还定义了一个懒标记对区间进行修改那么我们我们如果搜到的区间如果被包含在目标区间中那么我们就将这个区间节点中的懒标记修改一下然后返回不再往下搜了如果不完全包含的话就先将当前搜到区间的懒标记先传下去然后再执行进一步的递归。这里将懒标记传下去的操作就是pushdown那么pushdown具体怎么实现呢实际还要回到懒标记的意义上来懒标记意味着从当前区间往下所有的区间都需要进行这个修改当前区间是否执行这个修改无所谓目的是将修改传到叶子节点然后由叶子节点往上更新来实现。我们这里定义的话就直接将修改加到区间上懒标记表示下面的需要进行的修改。
#includebits/stdc.h
using namespace std;
const int N100010;
int a[N];
int n,m;
struct node
{int l,r;long long sum,add;
}tr[4*N];
void pushup(int u)
{tr[u].sum tr[u1].sumtr[u1|1].sum;
}
void pushdown(int u)
{tr[u1].addtr[u].add,tr[u1].sum (long long)(tr[u1].r-tr[u1].l1)*tr[u].add;tr[u1|1].addtr[u].add,tr[u1|1].sum (long long)(tr[u1|1].r-tr[u1|1].l1)*tr[u].add;tr[u].add0;
}
void build(int u,int l,int r)
{if(lr) tr[u]{l,r,a[l],0};else{tr[u]{l,r};int midlr1;build(u1,l,mid),build(u1|1,mid1,r);pushup(u);}
}
void modify(int u,int l,int r,int v)
{if(ltr[u].ltr[u].rr) {tr[u].sum (long long)(tr[u].r-tr[u].l1)*v;tr[u].addv;}else{pushdown(u);int midtr[u].ltr[u].r1;if(rmid) modify(u1,l,r,v);else if(lmid) modify(u1|1,l,r,v);else modify(u1,l,r,v),modify(u1|1,l,r,v);pushup(u);}
}
long long query(int u,int l,int r)
{if(ltr[u].ltr[u].rr) return tr[u].sum;pushdown(u);int midtr[u].ltr[u].r1;long long v0;if(lmid) vquery(u1,l,r);if(rmid) v query(u1|1,l,r);return v;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,a[i]);build(1,1,n);while(m--){char op[2];int l,r;scanf(%s%d%d,op,l,r);if(op[0]Q){coutquery(1,l,r)endl;}else{int v;scanf(%d,v);modify(1,l,r,v);}}
}
247. 亚特兰蒂斯247. 亚特兰蒂斯 - AcWing题库 图差不多是这个样子 单个算还好说重叠起来就很麻烦。所以这里引入一种全新的算法——扫描线 我们将图分成如上的区间显然在一个区间中面积就是区间长度(横坐标差)*区间中纵坐标覆盖的总长度。 假设有一根无限长的直线进行扫描显然当一个矩形最左边的边被扫到的时候那么就要开始计算面积了第二次被扫到的时候就不能再计算这个矩形了。这里我们可以通过对这段区间标记来处理令左边的标记为1右边的标记为-1那么刚好扫到右边的时候就不用再考虑它了。 区间长度倒是还比较好获得问题在于纵坐标覆盖的总长度该怎么看显然在一个区间中它是不变的那么我们可以一个区间一个区间地往后看。那么该如何维护呢这里有个特别妙地思路因为y是浮点数所以需要对y进行离散化而且我们用线段树维护的时候也并非用区间的端点维护区间而是在离散化后得到若干个点每两点之间的区间我们给它定一个序号然后我们用线段树的节点来维护每一个区间的序号这样说还是有点抽象见下图 我们看叶子节点每个叶子节点维护的实际是一个对应序号的区间。
然后再来考虑我们具体需要维护的值是什么首先我们要直到区间是否被标记才能进一步考虑是否需要把这段长度算上那么很显然我们需要一个cnt来标记这段区间的标记情况又因为一个矩形的左右边是对称的所以cnt的值恒大于等于0如果cnt0那么这段区间就会被考虑如果cnt0那么这段区间就不能再被考虑。
然后需要一个变量len来维护这段区间中被标记部分的总长度。
由于线段树维护的是区间的序号所以我们每次用到的只有根节点的len所以在更新的时候我们是会把cnt传到完全包含的区间部分去的。而且我们每次用的都是根节点的值所以只要它往上传是正确的那么就无所谓所以我们并不需要将父节点的cnt传到子节点去只要保证子节点的cnt被更新后将len的变化传到父节点去即可。所以一个节点被标记的意义就是这个节点能被表示的所有区间都被标记。
所以在pushup的时候 如果父节点被标记那么父节点的len自己用两端点更新一下就好所以我们更新区间的时候就需要pushup因为cnt发生了变化 如果父节点没有被标记那么就要看它是不是叶子节点 如果是叶子节点那么len就是0 否则就需要用它的子节点来更新一下它因为cnt可能传到它的子节点上去了。
所以我们是先递归然后再进行pushup这样才能实现从子节点往上在回溯的过程中更新父节点。至此本题相较于模板特殊的地方都讨论完了。
然后这里的离散化就用vector就行然后查找用二分。
另外需要记录一下左右边。
#includebits/stdc.h
using namespace std;
const int N10010;
struct edge{double x,y1,y2;int sta;
}seg[2*N];//每个矩形记录左右边
struct node{int l,r,cnt;double len;
}tr[8*N];//4*2*N
bool cmp(edge a,edge b)
{return a.xb.x;
}
int n;
vectordoublehy;//对y进行离散化
void pushup(int u)
{if(tr[u].cnt) tr[u].lenhy[tr[u].r1]-hy[tr[u].l];else if(tr[u].l!tr[u].r){tr[u].lentr[u1].lentr[u1|1].len;}else{tr[u].len0;}
}
void build(int u,int l,int r)
{tr[u]{l,r,0,0};if(lr) return;int midlr1;build(u1,l,mid),build(u1|1,mid1,r);
}
void modify(int u,int l,int r,int k)
{if(ltr[u].ltr[u].rr) {tr[u].cntk;pushup(u);}else{int midtr[u].ltr[u].r1;if(lmid) modify(u1,l,r,k);if(rmid) modify(u1|1,l,r,k);pushup(u);}
}
int find(double x)
{return lower_bound(hy.begin(),hy.end(),x)-hy.begin();
}
int main()
{int t0;while(~scanf(%d,n)){hy.clear();t;if(!n) break;int j0;for(int i1;in;i){double x1,y1,x2,y2;scanf(%lf%lf%lf%lf,x1,y1,x2,y2);seg[j]{x1,y1,y2,1},seg[j]{x2,y1,y2,-1};hy.push_back(y1),hy.push_back(y2);}sort(hy.begin(),hy.end());hy.erase(unique(hy.begin(),hy.end()),hy.end());build(1,0,hy.size()-2);sort(seg,seg2*n,cmp);double res0;for(int i0;i2*n;i){if(i) res (seg[i].x-seg[i-1].x)*tr[1].len;modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].sta);}printf(Test case #%d\n,t);printf(Total explored area: %.2lf\n,res);printf(\n);}
}
1277. 维护序列(活动 - AcWing) 思路这里和之前不同的地方就在不仅要对一段区间同时加上一个数还要对一段区间同时乘上一个数所以就涉及到先后顺序的问题了所谓先后怎么说呢实际上是父节点去更新子节点的时候对子节点产生的先后。因为子节点本身是有更新的那么它被父节点更新的时候是先加还是先乘呢 我们来分别讨论如果是先加再乘 (xa)*b 那么父节点的懒标记传过来的时候哪怕只有加c (xa)*bc 是没有办法变成x_*_的形式的所以先加再乘不合适 那么如果是先乘再加呢 x*ba 父节点的懒标记传过来的时候 x*bac (x*ba)*mulx*b*mula*mul 都是可以变成x*__的形式的所以我们就定义先乘再加。 那么更新的时候既有乘的操作又有加的操作实际上还是有点麻烦的所以我们这么来如果是加x的话就定义成*1和x, 如果是*x的话就定义成*x和0.这样写一个modify函数就够了。
#includebits/stdc.h
using namespace std;
const int N100010;
typedef long long ll;
int a[N];
int n,m,p;
struct node{int l,r;int sum,add,mul;
}tr[4*N];
void pushup(int u)
{tr[u].sum(tr[u1].sumtr[u1|1].sum)%p;
}
//(x*ab)*cdx*a*cb*cd
void eval(node u,int mul,int add)
{u.sum((ll)u.sum*mul(ll)(u.r-u.l1)*add)%p;u.add((ll)u.add*muladd)%p;u.mul(ll)u.mul*mul%p;
}
void pushdown(int u)
{eval(tr[u1],tr[u].mul,tr[u].add);eval(tr[u1|1],tr[u].mul,tr[u].add);tr[u].add0,tr[u].mul1;
}
void build(int u,int l,int r)
{if(lr) tr[u]{l,r,a[l],0,1};else{tr[u]{l,r,0,0,1};//反正子节点还要来更新它的int midlr1;build(u1,l,mid),build(u1|1,mid1,r);pushup(u);}
}
void modify(int u,int l,int r,int mul,int add)
{if(ltr[u].ltr[u].rr) {eval(tr[u],mul,add);}else{pushdown(u);int midtr[u].ltr[u].r1;if(lmid) modify(u1,l,r,mul,add);if(rmid) modify(u1|1,l,r,mul,add);pushup(u);}
}
int query(int u,int l,int r)
{if(ltr[u].ltr[u].rr) return tr[u].sum;pushdown(u);int midtr[u].ltr[u].r1;int v0;if(lmid) vquery(u1,l,r);if(rmid) v(vquery(u1|1,l,r))%p;return v;
}
int main()
{scanf(%d%d,n,p);for(int i1;in;i) scanf(%d,a[i]);build(1,1,n);scanf(%d,m);while(m--){int op,l,r,v;scanf(%d%d%d,op,l,r);if(op1)//*{scanf(%d,v);modify(1,l,r,v,0);}else if(op2)//{scanf(%d,v);modify(1,l,r,1,v);}else//q{coutquery(1,l,r)endl;}}
}
