数列分块1(学习）

题目传送门

适用范围：区间修改，单点查询。

思想：分块操作，将 $bk(block)$ 个数作为一组(一块)。

每次操作会涉及最多 $\dfrac{n}{bl}$ 个块和包括左右区间不完整最多 $2bl$ 个元素。

即每次操作的复杂度大约在： $O(\dfrac{n}{bl}+bl)$

根据均值不等式 $\rightarrow bl=\sqrt{n}$ 最合适。

总复杂度： $O(n\sqrt{n})$

树状数组做法待补 $\dots\dots$

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
int a[N],bk,n,tag[N],bl[N];
void add(int l,int r,int c){
    for(int i=l;i<=min(bl[l]*bk,r);i++) //左端不完整块暴力修改 
        a[i]+=c;
    if(bl[l]!=bl[r]) //防止加重. 
        for(int i=(bl[r]-1)*bk+1;i<=r;i++) //右端不完整块暴力修改 
            a[i]+=c;
        for(int i=bl[l]+1;i<=bl[r]-1;i++) //每块修改. 
            tag[i]+=c;
} 
int main(){
    scanf("%d",&n);bk=sqrt(n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) bl[i]=(i-1)/bk+1;
    for(int i=1,op,l,r,c;i<=n;i++){
        scanf("%d%d%d%d",&op,&l,&r,&c);
        if(!op) add(l,r,c);
        else printf("%d\n",a[r]+tag[bl[r]]);
    }
    return 0;
}

线段树做法：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=5e6+5;
struct node{ //结构体线段树板子. 
    int l,r,s,lz;//[l,r],sum,lzay tag 
}a[N];
void re(int x){ //refresh 更新和sum 
    a[x].s=a[x<<1].s+a[x<<1|1].s; 
}
void pushdown(int x){ //下放标记. 
    if(a[x].lz){
        a[x<<1].lz+=a[x].lz,a[x<<1|1].lz+=a[x].lz;
        a[x<<1].s+=(a[x<<1].r-a[x<<1].l+1)*a[x].lz;
        a[x<<1|1].s+=(a[x<<1|1].r-a[x<<1|1].l+1)*a[x].lz;
        a[x].lz=0;
    }
}
void build(int x,int l,int r){
    a[x].l=l,a[x].r=r,a[x].lz=0;
    if(l==r){
        scanf("%d",&a[x].s);
        return;
    } 
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
} 
void update(int x,int l,int r,int val){  ///update和query都需要pushdown 
     if(l<=a[x].l&&a[x].r<=r){ //更新. 
          a[x].s+=(a[x].r-a[x].l+1)*val;
         a[x].lz+=val;
         return; 
     }
     pushdown(x);
     int mid=(a[x].l+a[x].r)>>1;
     if(l<=mid) update(x<<1,l,r,val);
     if(r>mid) update(x<<1|1,l,r,val);
     re(x);
}
int  query(int x,int l,int r){
     if(l<=a[x].l&&a[x].r<=r) return a[x].s;
     else if(a[x].r<l||a[x].l>r) return 0;
     pushdown(x);
     int mid=(a[x].l+a[x].r)>>1;
     return query(x<<1,l,r)+query(x<<1|1,l,r);
}
int main(){
    int n;
    scanf("%d",&n);
    build(1,1,n);
    for(int i=1,op,l,r,val;i<=n;i++){
         scanf("%d%d%d%d",&op,&l,&r,&val);
         if(!op) update(1,l,r,val);
         else printf("%d\n",query(1,r,r));
    }
    return 0;
}