线段树，是一种支持点修点查，去修区查的高级数据结构，单词操作时间复杂度为O(log2点数)，非常的优秀
拉张图来解释一下线段树：
每个父节点的权值是两个子节点权值的和
好的。首先建一棵线段树我们来采用递归建树：先从根节点DFS遍历，然后返回后使用push_up函数累加——这样就可以保证线段树的性质
其次就是修改
如果是单点修改的话就从根节点向下找到该节点然后返回的时候沿途更新其祖先
如果是区间修改的话
引入：懒标记：LAZYTAG
如果一个个修改的话复杂度很高，所以当修改时应该找到比所选区间小或相等的一个或者几个区间，并使区间的交集为空，并集为所选区间
然后就是查询
单点查询就是从线段树的根走到最末一层，不多说
区间查询
和区修极其神似的，区查就是选几个。。。（上面有）的区间，累加和，作为答案，输出
想必通过我的解释，你一定没懂，啊不，懂了，所以，让我们来看代码——板子题，以及板子题的微调（板子还有个区间乘加，可是老登笔者还没有Ac（没做））
哦对了，线段树码量真多，（当然也有老登笔者菜的原因），但这不是重点
线段树一定要开4倍数组！！！！
点击查看代码
#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define int long long
using namespace std;
inline int read(){
int nb=0,f=1;
char c=getchar();
while(c>'9' || c<'0'){
if(c=='-'){
f=-f;
}
c=getchar();
}
while(c>='0' && c<='9'){
nb=nb*10+c-'0';
c=getchar();
}
return nb*f;
}
const int N=1e6+145;
struct nb{
int l,r,sum,tag;
nb(int a,int b,int c,int d):l(a),r(b),sum(c),tag(d){}
nb(){}
}tr[N<<2];
int n,q,wq,l,r,x;
int a[N];
inline void push_up(int p){
tr[p].sum=tr[lc].sum+tr[rc].sum;
}
inline void push_down(int p){
if(tr[p].tag){
tr[lc].tag+=tr[p].tag;
tr[rc].tag+=tr[p].tag;
tr[lc].sum+=tr[p].tag*(tr[lc].r-tr[lc].l+1);
tr[rc].sum+=tr[p].tag*(tr[rc].r-tr[rc].l+1);
tr[p].tag=0;
}
}
inline void bt(int p,int l,int r){//buildtree
tr[p]={l,r,a[l],0};
if(l==r){
return ;
}
int mid=(l+r)>>1;
bt(lc,l,mid);
bt(rc,mid+1,r);
push_up(p);
}
inline void wlgd(int p,int l,int r,int k){
if(tr[p].l>=l && tr[p].r<=r){
tr[p].tag+=k;
tr[p].sum+=k*(tr[p].r-tr[p].l+1);
return ;
}
int mid=tr[p].l+tr[p].r>>1;
push_down(p);
if(mid>=l) wlgd(lc,l,r,k);
if(mid<r) wlgd(rc,l,r,k);
push_up(p);
}
inline int query(int p,int l,int r){
if(l<=tr[p].l && r>=tr[p].r){
return tr[p].sum;
}
int res=0;
int mid=tr[p].l+tr[p].r>>1;
push_down(p);
if(mid>=l) res+=query(lc,l,r);
if(mid<r) res+=query(rc,l,r);
return res;
}
signed main(){
n=read(),q=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
bt(1,1,n);
// for(int i=1;i<=2*n;i++){
// cout<<tr[i].sum<<" ";
// }
for(int i=1;i<=q;i++){
cin>>wq;
if(wq==1){
l=read(),r=read(),x=read();
//cin>>l>>r>>x;
wlgd(1,l,r,x);
}
else{
l=read(),r=read();
//cin>>l>>r;
cout<<query(1,l,r)<<"\n";
}
}
return 0;
}
点击查看代码
#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define int long long
using namespace std;
int n,m,op,ll,rr;
const int N=2e5+10;
char c[N];
struct node{
int sum,tag,l,r;
}tr[N<<2];
void push_up(int p){
tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void push_down(int p){
if(tr[p].tag){
tr[lc].tag^=1;
tr[rc].tag^=1;
tr[lc].sum=tr[lc].r-tr[lc].l+1-tr[lc].sum;
tr[rc].sum=tr[rc].r-tr[rc].l+1-tr[rc].sum;
tr[p].tag=0;
}
}
void buildtree(int p,int l,int r){
tr[p]={0,0,l,r};
if(l==r){
if(c[l]=='1'){
tr[p].sum++;
}
return ;
}
int mid=l+r>>1;
buildtree(lc,l,mid);
buildtree(rc,mid+1,r);
push_up(p);
}
void update(int p,int l,int r){
if(tr[p].l>=l && tr[p].r<=r){
tr[p].tag^=1;
tr[p].sum=tr[p].r-tr[p].l+1-tr[p].sum;
return ;
}
int mid=tr[p].l+tr[p].r>>1;
push_down(p);
if(mid>=l) update(lc,l,r);
if(mid<r) update(rc,l,r);
push_up(p);
}
int query(int p,int l,int r){
int res=0;
if(tr[p].l>=l && tr[p].r<=r){
return tr[p].sum;
}
push_down(p);
int mid=tr[p].l+tr[p].r>>1;
if(mid>=l) res+=query(lc,l,r);
if(mid<r) res+=query(rc,l,r);
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>c[i];
}
buildtree(1,1,n);
for(int i=1;i<=m;i++){
cin>>op>>ll>>rr;
if(op==0){
update(1,ll,rr);
}
else{
cout<<query(1,ll,rr)<<"\n";
}
}
return 0;
}
好的，哪天闲的没事再来更个点修点查啥的
不过想必聪明的你会了区修区查之后一定也会点修点查了
拜拜~