线段树
线段树的构筑是自顶向下，还是自底向上？
在构筑的过程中，要维护统计值
对于sum[i]，i所代表的区间，拆分出两个区间后，编号如何确定？
设根节点是0还是1号，先1号吧，那两个孩子就是2*i与2*i+1
所以对于i号区间，sum[i]=sum[2*i]+sum[2*i+1]，要求2*i+1<4*n
这样应该就能把树的统计值初始化好了
那开始修改后呢？就是到底怎么返回查询区间的那个统计值？懒修改的思想，到底是什么？
对于构建，如何知道自己到了叶子节点？如果只是靠2*i+1<4*n知道了自己到达了叶子节点，那怎么知道自己的值该是多少？
就是说线段树的所有修改和查询的尺度都是固定好的，就是线段树每个节点拼起来的，而非由查询的区间所参与组成；查询区间只是说去决定最后的结果或修改是由线段树的哪些区间所组成，即对应完全包含的那个分支
#include<bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<long long>num(n),sum(4*n,0),lazy(4*n,0); for(int i=0;i<n;i++){ cin>>num[i]; } function<long long(int,int,int)> build=[&](int cur,int l,int r){ if(l==r){//知道了自己是叶子节点，然后从Num中取值 sum[cur]=num[l-1];//但是怎么知道当前的点，即在线段树当中的坐标，是第几个叶子节点？即num中的第几个元素？ return sum[cur]; } int mid=(l+r)>>1; sum[cur]=build(2*cur,l,mid)+build(2*cur+1,mid+1,r); return sum[cur]; }; auto push_down=[&](int cur,int l,int r){ int mid=(l+r)>>1; //相当于把lazy中寄存的待修改值，向子区间进行一次传递修改 lazy[2*cur]+=lazy[cur]; sum[2*cur]+=lazy[cur]*(mid-l+1); lazy[2*cur+1]+=lazy[cur]; sum[2*cur+1]+=lazy[cur]*(r-mid); lazy[cur]=0; }; //传参数的必须传区间编号，区间的左右边界吗？如果树长固定的话，知道区间编号也就能知道区间的左右边界吧？ //如果在向下递归时，不改变查询的边界？ function<void(int,int,int,int,int,long long)> add=[&](int cur,int l,int r,int ql,int qr,long long val){ //如果完全不包含 if(qr<l||ql>r){return;} //如果ql,qr完全包含l和r if(l>=ql&&r<=qr){//真的会出现这种情况吗？一开始不就是从最大空间往下递归的吗，那不应该始终保持ql和qr是l和r的子集？ lazy[cur]+=val; sum[cur]+=val*(r-l+1); return; } //部分包含，先实现本层的懒标记 push_down(cur,l,r); int mid=(l+r)>>1; //怎么选择修改区间？就是向下递归后的修改区间，现在是只知道在一半区间当中存在，那另一半是继续保持l或r，还是说区间边界，即mid或mid+1？如果查询区间刚好就完全处于一半呢，而且还是子集呢？ //在左一半存在 if(ql<=mid){ //int nqr=min(mid,qr); add(2*cur,l,mid,ql,qr,val); //sum[cur]+=val*(nqr-l+1);//落在左区间的元素数量 } //在右一半存在 if(qr>mid){ //int nql=max(mid+1,ql); add(2*cur+1,mid+1,r,ql,qr,val); //sum[cur]+=val*(r-nql+1); } sum[cur]=sum[2*cur]+sum[2*cur+1]; //这样写会有问题吗？比如qr超过了r，l超过了mid，这样在右区间有存在，但查询的边界不再是qr，而是r? //如何保证区间的处理是正确的？且逻辑通顺？ }; function<long long(int,int,int,int,int)> query=[&](int cur,int l,int r,int ql,int qr){ if(ql>r||qr<l){return 0LL;} if(ql<=l&&qr>=r){ return sum[cur]; } push_down(cur,l,r); int mid=(l+r)>>1; long long res=0; if(ql<=mid){ res+=query(2*cur,l,mid,ql,qr); } if(qr>mid){ res+=query(2*cur+1,mid+1,r,ql,qr); } return res; }; build(1,1,n); int flag,x,y; long long k; for(int i=0;i<m;i++){ cin>>flag; if(flag==1){ cin>>x>>y>>k; add(1,1,n,x,y,k); }else{ cin>>x>>y; cout<<query(1,1,n,x,y)<<endl; } } return 0; }P3373 【模板】线段树 2
这个相比原来就是多加了一个乘法
如果是区间加法，那可以把区间长度的复杂度缩减到O1，针对加和
但如果是乘法，如果区间里的每个元素都变成原来的X倍，那结果应该也是原来的X倍
但和加法肯定有一个次序的要求
难道对于某个区间进行乘法时，要先结算一次lazy吗？
那乘法的修改如何做？也是懒标记？
有点数论的意思在；就是先约定对于区间的加和形态，然后考虑每种操作后，如何影响这个形态
#include<bits/stdc++.h> using namespace std; int main(){ int n,q,m,flag,x,y,k; cin>>n>>q>>m; vector<int>num(n); vector<long long>sum(4*n),add(4*n,0),mul(4*n,1); for(int i=0;i<n;i++){cin>>num[i];} function<int(int,int,int)> build=[&](int p,int l,int r){ if(l==r){ sum[p]=num[l-1]; return sum[p]; } int mid=(l+r)>>1; sum[p]=(build(p*2,l,mid)+build(p*2+1,mid+1,r))%m; return sum[p]; }; auto push_down=[&](int p,int l,int r){ int mid=(l+r)>>1; //向下更新孩子 mul[p*2]*=mul[p]; mul[p*2]%=m; add[p*2]=(add[p*2]*mul[p]+add[p])%m; sum[p*2]=(sum[p*2]*mul[p]+add[p]*(mid-l+1))%m; mul[p*2+1]*=mul[p]; mul[p*2+1]%=m; add[p*2+1]=(add[p*2+1]*mul[p]+add[p])%m; sum[p*2+1]=(sum[p*2+1]*mul[p]+add[p]*(r-mid))%m; mul[p]=1; add[p]=0; }; function<void(int,int,int,int,int,int)> update_mul=[&](int p,int l,int r,int ql,int qr,int val){ if(ql>r||qr<l){return;} if(ql<=l&&qr>=r){ mul[p]*=val; mul[p]%=m; add[p]*=val; add[p]%=m; sum[p]=(sum[p]*val)%m; return; } int mid=(l+r)>>1; push_down(p,l,r); if(ql<=mid){ update_mul(2*p,l,mid,ql,qr,val); } if(qr>mid){ update_mul(2*p+1,mid+1,r,ql,qr,val); } sum[p]=(sum[p*2]+sum[p*2+1])%m; }; function<void(int,int,int,int,int,int)> update_add=[&](int p,int l,int r,int ql,int qr,int val){ if(ql>r||qr<l){return;} if(ql<=l&&qr>=r){ add[p]+=val; add[p]%=m; sum[p]+=(r-l+1)*val; sum[p]%=m; return; } int mid=(l+r)>>1; push_down(p,l,r); if(ql<=mid){ update_add(2*p,l,mid,ql,qr,val); } if(qr>mid){ update_add(2*p+1,mid+1,r,ql,qr,val); } sum[p]=(sum[p*2]+sum[p*2+1])%m; }; function<int(int,int,int,int,int)> query=[&](int p,int l,int r,int ql,int qr){ if(ql>r||qr<l){return 0;} if(ql<=l&&qr>=r){return int(sum[p]%m);} int mid=(l+r)>>1; long long res=0; push_down(p,l,r); if(ql<=mid){ res+=query(2*p,l,mid,ql,qr); } if(qr>mid){ res+=query(2*p+1,mid+1,r,ql,qr); } return int(res%m); }; build(1,1,n); for(int i=0;i<q;i++){ cin>>flag; if(flag==1){ cin>>x>>y>>k; update_mul(1,1,n,x,y,k); } else if(flag==2){ cin>>x>>y>>k; update_add(1,1,n,x,y,k); } else{ cin>>x>>y; cout<<query(1,1,n,x,y)<<endl; } } return 0; }P3870 [TJOI2009] 开关
统计值就是这个区间里有多少灯是开的
对于修改
当完全覆盖时，先是知道当前这个区间有多少开的，即此时的统计值cnt
然后改写为区间长度-cnt
也没有懒修改了；不对，好像还是要去修改一下子数组里的sum;还是保留一个lazy数组，标识是否发生了反转，每次都是取反操作；
如果要push_down时，只有发生了反转，即为true时，才去反转子数组，否则相当于无事发生；
当部分覆盖时，就继续递归
由于每次操作都是反转，所以感觉好像也没有必要保留每个电灯的状态，只要保留区间整体亮着的电灯计数就行了
可以理解为，线段树缩减复杂度的核心就在于它将任意区间，最终都将变成一开始已划分好区间的拼凑组合，然后最终操作都落于完全覆盖时的那个分支
所以加速的优化，关键就在于在完全覆盖的那个分支，不管区间多长，都一定要是O1的实现
然后对于那个lazy，对于add和mul的情况，如果完全实现，其实还是On，但关键在于它没有完全地，一一地去赋值，而是直接先对区间整体打个标记，当之后的修改具体到这个精细区间后，再落实lazy，这样表面上对每个区间的修改就都是O1了
P1438 无聊的数列
这个每次查询，是查具体的单个值
感觉线段树效果都不一定好
而且对于lazy向下push_down的操作都不好实现
对于sum的修改可以直接用等差求和公式
那lazy保存什么？也是求和？那他在Push_down的时候怎么拆分到两个左右区间？
知道各自区间长度，和区间总和，好像能？推一推公式
那lazy记录的其实还是区间的和
然后知道区间长度，即这个等差数列的长度，然后应该是能知道公差之类的信息，总之就是应该能求出来分给左右区间的和的值
然后往左右区间传递即可
问题在于，已知区间和和区间长度，如何求解分给左区间的部分？右区间就是总和减去分给左区间的就行
这样做的正确性，应该还是在于加法的结合律
#include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m,l,r,k,d,op; cin>>n>>m; vector<long long>sum(4*n,0),lazy_first(4*n,0),lazy_d(4*n,0); vector<int>num(n); function<long long(int,int,int)> build=[&](int cur,int l,int r){ if(l==r){ sum[cur]=num[l-1]; return sum[cur]; } int mid=(l+r)>>1; sum[cur]=build(2*cur,l,mid)+build(2*cur+1,mid+1,r); return sum[cur]; }; function<void(int,int,int)>push_down=[&](int cur,int l,int r){ int mid=(l+r)>>1,lenl=mid-l+1,lenr=r-mid; long long r_first=lazy_first[cur]+(mid+1-l)*lazy_d[cur]; lazy_first[cur*2]+=lazy_first[cur]; lazy_d[cur*2]+=lazy_d[cur]; sum[cur*2]+=(1LL*lenl*lazy_first[cur]+1LL*lenl*(lenl-1)/2*lazy_d[cur]); lazy_first[cur*2+1]+=r_first; lazy_d[cur*2+1]+=lazy_d[cur]; sum[cur*2+1]+=(1LL*lenr*r_first+1LL*lenr*(lenr-1)/2*lazy_d[cur]); lazy_first[cur]=0; lazy_d[cur]=0; }; function<void(int,int,int,int,int,int,int)>update=[&](int cur,int l,int r,int ql,int qr,int k,int d){ if(ql>r||qr<l){return;} if(ql<=l&&qr>=r){ int len=r-l+1; sum[cur]+=(1LL*len*(k+(l-ql)*d)+1LL*len*(len-1)/2*d); lazy_first[cur]+=(k+1LL*(l-ql)*d); lazy_d[cur]+=d; return; } push_down(cur,l,r); int mid=(l+r)>>1; if(ql<=mid){update(cur*2,l,mid,ql,qr,k,d);} if(qr>mid){update(cur*2+1,mid+1,r,ql,qr,k,d);} sum[cur]=sum[cur*2]+sum[cur*2+1]; }; function<long long(int,int,int,int)>query=[&](int cur,int l,int r,int q){ if(l==r){return sum[cur];} int mid=(l+r)>>1; push_down(cur,l,r); if(q<=mid){ return query(cur*2,l,mid,q); } else{ return query(cur*2+1,mid+1,r,q); }//对于q==mid的情况，能否提前return? }; for(int i=0;i<n;i++){cin>>num[i];} build(1,1,n); for(int i=0;i<m;i++){ cin>>op; if(op==1){ cin>>l>>r>>k>>d; update(1,1,n,l,r,k,d); }else{ cin>>l; cout<<query(1,1,n,l)<<endl; } } return 0; }P1253 扶苏的问题
统计值肯定是max
然后加的区间操作，是不改变这个区间的max的
只有覆写可能会改变
对于build时，
max=max(左，右）
lazy存什么？
如果执行覆写操作，当完全包含时，要把max改为x，子数组也都是
部分包含时，先分治，
最后取一次max
对于加操作，对于完全包含，max在原来基础上+x
其实和执行覆写时差不多
关键在于lazy存什么？是在覆写时存覆写操作，还是存加和操作？
这两个操作肯定不能像加和乘一样并存，用两个lazy数组来记录
感觉就是存加和，当要覆写时，就必须执行一次区间的ON操作，覆写max以及清空lazy
就是说还是两个数组，但是在执行覆写操作时，优先级很高，要覆写掉add，使其为0
然后add就不改set
这样当push_down时，如果存在add，就一定是覆写完后的add修改
#include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,q; cin>>n>>q; vector<long long>num(n),maxNum(4*n),lazy_set(4*n,LLONG_MIN),lazy_add(4*n,0); for(int i=0;i<n;i++){cin>>num[i];} auto build=[&](auto&& self,int cur,int l,int r){ if(l==r){ maxNum[cur]=num[l-1]; return maxNum[cur]; } int mid=(l+r)>>1; maxNum[cur]=max(self(self,cur*2,l,mid),self(self,cur*2+1,mid+1,r)); return maxNum[cur]; }; build(build,1,1,n); auto push_down=[&](int cur,int l,int r){ //int mid=(l+r)>>1; if(lazy_set[cur]!=LLONG_MIN){ lazy_set[cur*2]=lazy_set[cur]; lazy_add[cur*2]=0; maxNum[cur*2]=lazy_set[cur]; lazy_set[cur*2+1]=lazy_set[cur]; lazy_add[cur*2+1]=0; maxNum[cur*2+1]=lazy_set[cur]; lazy_set[cur]=LLONG_MIN; } if(lazy_add[cur]!=0){ lazy_add[cur*2]+=lazy_add[cur]; maxNum[cur*2]+=lazy_add[cur]; lazy_add[cur*2+1]+=lazy_add[cur]; maxNum[cur*2+1]+=lazy_add[cur]; lazy_add[cur]=0; } }; auto update_set=[&](auto&& self,int cur,int l,int r,int ql,int qr,long long val){ if(ql>r||qr<l){return;} if(ql<=l&&qr>=r){ lazy_set[cur]=val; lazy_add[cur]=0; maxNum[cur]=val; return; } int mid=(l+r)>>1; push_down(cur,l,r); if(ql<=mid){self(self,cur*2,l,mid,ql,qr,val);} if(qr>mid){self(self,cur*2+1,mid+1,r,ql,qr,val);} maxNum[cur]=max(maxNum[cur*2],maxNum[cur*2+1]); }; auto update_add=[&](auto&& self,int cur,int l,int r,int ql,int qr,long long val){ if(ql>r||qr<l){return;} if(ql<=l&&qr>=r){ lazy_add[cur]+=val; maxNum[cur]+=val; return; } int mid=(l+r)>>1; push_down(cur,l,r); if(ql<=mid){self(self,cur*2,l,mid,ql,qr,val);} if(qr>mid){self(self,cur*2+1,mid+1,r,ql,qr,val);} maxNum[cur]=max(maxNum[cur*2],maxNum[cur*2+1]); }; auto query=[&](auto&& self,int cur,int l,int r,int ql,int qr){ if(ql>r||qr<l){return LLONG_MIN;} if(ql<=l&&qr>=r){ return maxNum[cur]; } int mid=(l+r)>>1; push_down(cur,l,r); long long res=LLONG_MIN; if(ql<=mid){res=max(res,self(self,cur*2,l,mid,ql,qr));} if(qr>mid){res=max(res,self(self,cur*2+1,mid+1,r,ql,qr));} return res; }; int l,r,op; long long x; for(int i=0;i<q;i++){ cin>>op; if(op==1){ cin>>l>>r>>x; update_set(update_set,1,1,n,l,r,x); } else if(op==2){ cin>>l>>r>>x; update_add(update_add,1,1,n,l,r,x); } else{ cin>>l>>r; cout<<query(query,1,1,n,l,r)<<endl; } } return 0; }P4513 小白逛公园
对于操作1，是说在这个区间内部的最大连续区间和
然后对于操作2，是说只修改单个值
对于朴素线段树，这些操作都像升级了一样，更刁钻了
首先对于操作2，这意味着每次操作都会落实到具体的点上，也就没有懒修改一说了
其次，对于操作1，即线段树所要维护的值，某个区间里的最大连续区间和，也不好维护，在区间里元素值改变后，如何在O1时间内更改也不好说
现在几乎完全没思路，也不是很想想，怎么做？思路是什么？
