题解：P3368 【模板】树状数组 2

· · 题解

目录

前言

本篇由 easy42 编写。

这是一篇数据结构分块题解。

算法介绍

分块，是一种暴力数据结构。它能以比线段树差，比暴力好的复杂度解决问题，时间复杂度通常是 O(m \sqrt n) 的，适合解决 n=m=10^5 的问题。

分块与线段树的不同之处是：分块是把序列分为一个个小块，而线段树则把序列建成一颗二叉树，每个节点存储区间值。

线段树一般只能解决具有合并性的问题，然而分块可以更灵活，更暴力的解决问题。

而且分块编码相对较为简单，在考场上可以发挥优势。

正确性证明

分块的思想可以概述为：整块统一处理，散块暴力统计。

分块的步骤是这样的：先把序列分成长度为 \lfloor \sqrt n\rfloor 个块，为什么分这个值后面会说。

如果 \sqrt n 的值是一个整数，则一共有刚好 \sqrt n 个块。

如果 \sqrt n 的值不是一个整数，后面会多出一个散块。

对于每个块，维护它的修改标记，以及序列中每个数的值。

这题分为两个操作：

  1. 区间修改
  2. 单点查询

在区间修改时，区间 [l,r] 可能会跨越多个块，如果是整块，对它的修改标记加上 k，散块则对原数组的元素加上 k。

在单点查询时，直接把原数组的元素加上这个块的修改标记就好了。

分析一下，我们既要遍历所有块的元素，也要遍历序列中所有的块，此时的时间复杂度为 O(m(\frac{n}{t}+t))，其中 t 为块的长度。当块长度取到 \sqrt n 时，有较好的时间复杂度 O(m \sqrt n)。

代码实现

初始化

首先，要确定把块的长度 block 设为 \lfloor \sqrt n \rfloor。

int block=sqrt(n);//块长

块的个数 t。

int t=n/block;//块的个数
if(n%block) t++;//增加散块

需要维护每个块的开头与结尾。

for(int i=1;i<=t;i++){
    head[i]=(i-1)*block+1;//是上个块的开头加一
    tail[i]=i*block;
}

请注意，最后一个块的末尾不能超过 n。

tail[t]=n;

以及使用数组 cnt 确定每个块所归属的位置。

for(int i=1;i<=n;i++){
    cnt[i]=(i-1)/block+1;
}

初始化完成。

区间修改

如果在同一块内，暴力修改即可。

if(cnt[x]==cnt[y]){
    for(int i=x;i<=y;i++){
        a[i]+=k;
    }
}

如果不在同一块内，先处理整块，再处理散块。

如果是整块，直接修改标记。

for(int i=cnt[x]+1;i<=cnt[y]-1;i++){
    add[i]+=k;
}

散块暴力更新：

for(int i=x;i<=tail[cnt[x]];i++){
    a[i]+=k;
}
for(int i=head[cnt[y]];i<=y;i++){
    a[i]+=k;
}

单点查询

直接把当前值加上块的修改标记就行了。

cout<<a[x]+add[cnt[x]]<<endl;

总代码：

#include<bits/stdc++.h> 
using namespace std;
#define int long long
int n,m,add[1000005],a[1000005],head[1000005],tail[1000005],cnt[1000005];
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int block=sqrt(n);
    int t=n/block;
    if(n%block) t++;
    for(int i=1;i<=t;i++){
        head[i]=(i-1)*block+1;
        tail[i]=i*block;
    }
    tail[t]=n;
    for(int i=1;i<=n;i++){
        cnt[i]=(i-1)/block+1;
    }
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int x,y,k;
            cin>>x>>y>>k;
            if(cnt[x]==cnt[y]){
                for(int i=x;i<=y;i++){
                    a[i]+=k;
                }
            }
            else{
                for(int i=cnt[x]+1;i<=cnt[y]-1;i++){
                    add[i]+=k;
                }
                for(int i=x;i<=tail[cnt[x]];i++){
                    a[i]+=k;
                }
                for(int i=head[cnt[y]];i<=y;i++){
                    a[i]+=k;
                }           
            }
        }
        else{
            int x;
            cin>>x;
            cout<<a[x]+add[cnt[x]]<<endl;
        }
    }
    return 0;
}

后记

点个赞吧！