_pks 'w blog

_pks 'w blog

除了勇气,我什么都不缺。

Senior Data Structure高级数据结构初步·详解分块思想与树状数组

posted on 2018-02-13 05:13:26 | under 数据结构学习 |

一、浅析数据结构之用处和高级数据结构之特性

数据结构者,谓之数据之关系。单论数据特性,也不过是数据之间的存储方式罢。但要说更深层次之作用,是运用其存储之特性,建立数学之模型,更方便地才处理数据尔

以上是鲁迅同志说的(鲁迅: $exm$ ???),其实一切的数据结构不过就是一种用于处理数据的、成熟的、合理的结构封装。较低级的数据结构不会支持什么操作,仅是维护自身的存储秩序;而高级数据结构则可以支持许多操作——其实也不过是维护自身数据的秩序而已,只不过在维护其自身秩序的同时,由于其本身结构复杂且特点鲜明,所以会产生许多很优化的算法。 (鲁迅:看在你讲得这么好饶了你!)

而今天我们主要介绍有关 $RMQ$ 、 $RSQ$ 问题的、较为基础的高级数据结构。

二、先来介绍分块思想吧

(一)基本性质与证明

其实从本质上来讲,分快更像是一种思想。分块,顾名思义,就是将一个区间分成几块,然后对于每个询问,整合一个或者多个甚至全部区间的信息。但是在这种整合不是随便整合,必须要有技巧、有目的地整合,才会减小时间复杂度。

先看一道例题:

现在你有一个长度为 $n$ 的序列,有 $m$ 个操作:

1.修改某位置的元素的值

2.将一段区间的元素加上或减去一个值。

3.求一段区间的元素的最大值。

$n$ , $m$ ≤ $50000$

让我们考虑分块: 首先第一步,进行区间划分,在这一步我们考虑将整个序列划分成 $\sqrt{n}$ 块,这可以使得其总查询时间最快

证明:

对于搜查整个序列中的一段区间,设这段区间内的完整分块块数是 $C$ 块,每一段均匀的分块都 $S$ 个元素,那么这一段区间的最复杂形式为:有 $C$ 个完整区间,并且闭区间[ $l$ , $r$ ]还在两端包括有不完整的分好的块:

——|—【————|——————|——————|————】—|————

上图中【】表示区间,|与|之间表示分好的均匀块(qwq博主不知道怎么画精美的图啦)

我们可以发现该区间内有 $C$ 段完整区间, $2$ 段不完整区间;而同时,不完整区间的元素数量之和,绝对小于等于 $2S$ ;那么我们对于这一个区间而言,共需要进行最多 $C+2S$ 次查询——因为一个分块可以供给块内所有元素的信息。那么查询的时间复杂度便是 $O$ ( $C+2S$ ),从渐进意义上来讲,时间复杂度为 $O$ ( $C+S$ ),渐进整合后便是 $O(max(C,S))$ (渐进的时间复杂度,可以认为等于对数值改变影响最大的数值的复杂度

在知道这一点之后,我们可以这么想:因为 $C\times{S}$ + $2S$ >= $r-l+1$ ,所以我们可以近似地看做有 $C\times{S}$ = $r-l+1$ ,所以在同一区间内 $C×S$ 之积可以看作是个定值。那么当且仅当 $S$ = $C$ 时,才会使得 $max$ ( $C$ , $S$ )最小,此时 $S$ = $C$ = $\sqrt{n}$ 。

(二)分块的运行机制

首先就是确立所分的块与被包含元素之间的关系,我们在此用一个 $belong$ 数组记录每个点与所分的块之间的关系,同时进行区间记录。

    int n,a[MAXN],belong[MAXN];
    int S,C=0,st[MAXN],ed[MAXN];//sum[MAXN],ma_x[MAXN],mi_n[MAXN]; 
    /*
    n:元素个数,a[]:元素,belong[]:每个元素所属的块的编号 
    S:每个块有多少元素 C:分块个数 st/ed:每个块的左边界、右边界 
    sum[MAXN]/ma_x[MAXN]/mi_n[MAXN]用于记录区间信息 
    */ 
    void pretreat()
    {
        S=int(sqrt(double(n)));
        for(int i=1;i<=n;i+=S){
            st[++C]=i;
            ed[C]=min(i+S-1,n);//有可能会越界(sqrt必然有精度误差) 
        }
        for(int i=1;i<=C;i++)
            for(int j=st[i];j<=ed[i];j++)
                {
                belong[j]=i;//初始化belong 
                /*
    //区间操作  sum[i]+=a[j];
                ma_x[i]=max(ma_x[i],j);
                */
                }
    }

其次便是区间修改&单点修改:由于区间操作只能针对于某个已经被分好的块,所以对于某些不完整区间的改动,需要进行单点修改。

对于区间修改,还有一点,为了帮助我们对区间讯息的整合,所以会引进一个 $delta mark$ ,记录某个区间整体的变化情况。 注意:当且仅当一个块被统一修改,才会改变这个。块的 $delta$ 。

//区间单点修改 ,此处以求区间和为例 
    inline void updata_single(int x,int k)
    {
        a[x]+=k;
        sum[belong[x]]+=k;
    }

    //区间修改,同上
    int delta[MAXN];//用于记录一个!完整!区间的修改 
    void updata_range(int x,int y,int k)
    {
        int l=belong[x],r=belong[y];
        if(l==r&&st[l]==x&&st[r]==y)
        {delta[l]=k; return ;}//ma_x[]
        //这个if纯粹是为了减少底下的运算,毕竟判断只有O(1) qwq
        else
        {
            for(int i=x;i<=ed[l];i++)
                updata_single(i,k);//如果不是完整区间,就单点修改 
            if(st[l]>x&&st[r]<y)return ; 
            //如果查询区间被某个块完全包含且不相等,
            //不需要进行以下操作 
            for(int i=st[r];i<=y;i++)
                updata_single(i,k);
            //如果所查询区间与块有交集且不想等
            //不需进行以下操作 
            for(int i=l+1;i<r;i++)
                delta[i]+=k;;
        }
    }

紧接着就是区间询问了,此时我们的 $delta$ 就派上用场啦!

    int query(int x,int y)//依然为区间和 
    {
        int l=belong[x],r=belong[y],ans=0;
        if(l==r){
            for(int i=x;i<=y;i++)
                ans+=a[i]+delta[belong[i]];
        }
        else{
            for(int i=x;i<=ed[l];i++)
                ans+=a[i]+delta[belong[i]];
            for(int i=l+1;i<r;i++)
                ans+=sum[i]+delta[i]*(ed[i]-st[i]+1);
                //对于每个区间的O(1)运算 
            for(int i=st[r];i<=y;i++)
                ans+=a[i]+delta[belong[i]];
        }
        return ans;
    }

我们会发现,对于一个分块程序来说,期望的时间总复杂度为:O( $\sqrt{n}$ * $m$ )的,对于 $50000$ 来说完全能跑开

三、树状数组浅谈

(一)关于树状数组的正确释义 $emmmm$

首先要知道一个很重要的点:

树状数组用的是树结构的思想(也就是树型逻辑结构),而不是真正的“树形结构”,初学者不要被强行拉入坑啊qwq(换句话说,从某种意义上,树状数组跟树其实——————没有特别大的关系)

那它为什么被叫作树状数组呢qwq?

(二)树状数组的存储特点

首先解释,树状数组支持的操作:1、区间和、区间异或和、区间乘积和 $RMQ$ (显然,支持的操作都具有交换律,这也算是树状数组的一大特性吧)2、单点修改(朴素的树状数组结构不支持区间修改,当然也可以普及成区间修改结构 $emm$ 但我们先不提

$emmmm$ 那为什么不直接用前缀和或者差分数组呢?

我们知道,前缀和数组的维护是 $O$ ( $n$ )的,查询、修改是 $O$ ( $1$ )的,然而,树状数组的维护却是 $O$ ( $logn$ )的。并且查询、修改也是 $O$ ( $1$ )的——这便是一个很大的优化。

等等, $logn$ ?有点眼熟诶。再提示提示,这个 $log$ 实际意义其实是 $log$ 以 $2$ 为底———————

对,没猜错,就是二进制表示法,也就是二叉树上数据之间的特殊逻辑关系!

实际上,对于树状数组 $tree$ 的每一个i,其实际意义应该为:算上其本身的讯息,总共存储了 $2^k$ 个元素的信息,其中 $k$ 表示 $i$ 在二进制下,末尾零的个数,同时也可以表示最小的含1位的二进制权值——换句话讲, $2^k$ 即可表示成:对于每个二进制意义下的i,从最末位数 $k+1$ 位,保留这 $k+1$ 位并删除 $k+1$ 位以左的所有数位上的数,留下的新二进制数的实际大小。

晕了?从头来看这张图:

(10)(2)

1: 1

2: 10

3: 11

4: 100

5: 101

6: 110

7: 111

8:1000

结合这张二进制转换表,是不是看出什么规律来了?对于上面的加粗 $emmmm$ 多读几遍还是会读懂的(毕竟只是个找规律啊 $qwq$ )

而对于每一个x的最低含一位,即上文中的 $2^k$ ,可以借助一个 $lowbit$ 函数实现——而这个的实现方式是很玄学的:

    inline int lowbit(int x)
    {
        //return (x^(x-1))&x;
        return x&(-x);
    }

上文代码中给了两种不同的实现方式,而这两种中,有一种是通过数学+二进制的方式得出,另一种则是通过计算机编码特性得出 $emmm$ 我实在懒得证了

(三)树状数组的建立、维护和查询

建立:此处拿求区间和为样例

void build() 
{
for(int i=1;i<=n;i++)       
{cin>>a[i];tree[i]=i;}//一开始先赋初值
}

维护:看注释

void updata(int x,int k)
{
    for(;x<=n;x+=lowbit(x))
        tree[x]+=k;
//此处可以如是想:lowbit取出的是当前x的最低含一位
//权值位,相加后等于向高位进位,并且已有的数位永远为零
//这就可以推出:每当x值+=lowbit(x)时,都会有进位,并且
//进位后的新x值一定包含所有原来的x值,也就是说,这一步
//充分地向上进位,达到区间和更新的目的。 
}

询问:从大到小枚举,比较方便。

    long long query(int x){
        int ans;
        for(;x;x-=lowbit(x))
            ans=ans+tree[x];
        return ans;
    }

整合:相减即可

    inline long long my_union(int x,int y)
    {
        return query(x)-query(y-1);
     }

$SO$ ,每次操作的复杂度均为 $O(logn)$