Archie

区间加和单点查询

很简单的思路就是$O(sqrt{n})修改和o(1)$查询，就像线段树一样搞。一个tag

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
int be[50005];
int len;
int x,y,z,k;
int a[50004];
int tag[50004];
void add(int l,int r,int c){
    for(int i=l;i<=min(r,be[l]*len);++i){
        a[i]+=c;
    }
    if(be[l]!=be[r]){
        for(int i=(be[r]-1)*len+1;i<=r;++i){
            a[i]+=c;
        }
    }
    for(int i=be[l]+1;i<be[r];++i){
        tag[i]+=c;
    }
    return ;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    len=sqrt(n);
    for(int i=1;i<=n;++i){
        be[i]=(i-1)/len+1;
    }
    for(int i=1;i<=n;++i){
        scanf("%d%d%d%d",&x,&y,&z,&k);
        if(x==0){
            add(y,z,k);
        }else{
            cout<<a[z]+tag[be[z]]<<endl;;
        }

    }
    return 0;
}

或者说差分，变成单点修改区间查

#include
#include
#include
#include
#include
using namespace std;
int n;
int a[100005];
int be[100006];
int len;
int cha[1000006];
int sum[100006];
int k,x,y,z;
void xiu(int x,int c){
    cha[x]+=c;
    sum[be[x]]+=c;
}
int query(int l,int r){
    int ans=0;
    if(be[l]==be[r]){
        for(int i=l;i<=r;++i){
            ans+=cha[i];        
        }
    }else{
        for(int i=1;i