P3374 【模板】树状数组 1

Posted Wed Mar 18 2020. 2510 words. 13 min read.

This article was last updated on days ago, the information described in the article may be outdated.

题目

[1]

题目描述

如题,已知一个数列,你需要进行下面两种操作:

  • 将某一个数加上 xx
  • 求出某区间每一个数的和

输入格式

第一行包含两个正整数 n,mn,m,分别表示该数列数字的个数和操作的总个数。

第二行包含 nn 个用空格分隔的整数,其中第 ii 个数字表示数列第 ii 项的初始值。

接下来 mm 行每行包含 33 个整数,表示一个操作,具体如下:

  • 1 x k 含义:将第 xx 个数加上 kk
  • 2 x y 含义:输出区间 [x,y][x,y] 内每个数的和

输出格式

输出包含若干行整数,即为所有操作 22 的结果。

输入输出样例

输入 #1

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

输出 #1

14
16

说明/提示

【数据范围】

对于 30%30\% 的数据,1n81m101 \le n \le 8,1\le m \le 10

对于 70%70\% 的数据,1n,m104;1\le n,\,m\le10^4;

对于 100%100\% 的数据,1n,m5×1051\le n,m \le 5\times 10^5

样例说明:

故输出结果 14、16

(写这篇呢其实是因为自己已经不会树状数组了,正好借此机会复习下 QAQ)

题解

树状数组

首先需要了解什么是 树状数组

树状数组用的是树结构的思想,即树型逻辑结构,但他不是树形结构啦

特点

树状数组 (Binary Indexed Tree(B.I.T), Fenwick Tree)是一个查询和修改复杂度都为 og(n) 的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在 log(n) 的复杂度下进行范围修改,但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。

对于这题,简单来说就是单点修改区间查询,一般地,树状数组不支持区间修改单点差选,但是我们也有办法让他支持…

树状数组的优势就在于其维护的时间复杂度为 O(logn)O(log \, n) ,而类似的前缀和数组维护的时间复杂度为 O(n)O(n),两者的查询都是 O(1)O(1)

(说到这我就想起来某次校内赛的xzt买煎饼。。。。还好我拿了20分)

前置知识

lowbit

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

十进制二进制
11
210
311
4100
5101
6110
7111
81000
91001
101010

图文并茂之后有没有看出点什么 QAQ

记得当时学的时候,在学校大佬的帮助下才理解了这些东西,可能我比较菜吧

没看出来就多看几遍吧 好像也还是看不出来,那就记下来结论吧

对于每一个 xx 的最低含一位,即上文中的 2k2^k,可以借助一个 lowbitlowbit 函数实现 emmm 一个极其玄学的东西

再把 lowbit 说简单点就是

把一个整数变成二进制,从右往左找到第一个1,然后返回这个1所表示的十进制值。

玄学公式登场 x & -x

举个例子

4=100,4=011+1=100 100&100=100=4 lowbit(4)=44 = 100,\,-4 = 011 + 1 = 100\\ ~\\ \because100\,\&\,100=100=4 \\ ~\\ \therefore lowbit(4)=4\\

int lowbit(int x) {
return x & -x; //就是这么玄学
}

为什么要这样干呢

我们先列出 1~8 的 lowbitlowbit

1  2  1  4  1  2  1  81\;2\;1\;4\;1\;2\;1\;8

我们让 C[i]C[i] 管理 A[ilowbit(i)+1,i]A[i-lowbit(i)+1,\,i] 这段区间,如下图

那么我们把某个点 +x+x 的时候只需要把能管到这个点的都 +x+x 就好啦,那我们如何找哪些能管到我们修改的点呢,这时候就需要 lowbitlowbit

前缀和

一维前缀和

现有一个长度为 NN 的序列 AA,需要进行 MM 次操作,每次操作选取从 AiA_iAjA_jji+1j-i+1 个数并求出他们的总和 (N 和 M 可以很大)

例:

N=9  A={3,1,4,1,5,9,2,6,5}N=9,\;A=\{3,1,4,1,5,9,2,6,5\}

如果按照题意暴力,最坏情况下时间复杂度 O(n×m)O(n\times m)(是这个吗,我咋感觉时间复杂度好像大概可能不是这个QAQ)

反正时间复杂度挺高的就对了

那我们可以新建一个数组 BB ,其中 Bi=Bi1+AiB_i=B_{i-1} +A_i

此时我们需要求 aiaja_i-a_j 的总和,意会下,只需要求 BjBi1B_j-B_{i-1} 就好啦

很明显,利用前缀和的方法,因为B数组是在读入时进行处理,可以看作不需要时间,而查询的时间复杂度就是 O(1)O(1)

二维前缀和

一维前缀和会了二维的也很简单

A=[566146342417094624]  B=[5111718212781826]A= \left[ \begin{matrix} 5 & 6 & 6 & 1 & 4 & 6\\ 3 & 4 & 2 & 4 & 1 & 7 \\ 0 & 9 & 4 & 6 & 2 & 4 \end{matrix} \right] \; B= \left[ \begin{matrix} 5 & 11 & 17 & 18 & 21 & 27\\ 8 & 18 & 26 & \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \end{matrix} \right]

若我们要求 x1,y1x_1,\,y_1x2,y2x_2,\,y_2 两点所围成矩形内数字的和
公式 sum=Bx2,y2Bx2,1B1,y1+Bx11,y11sum=B_{x_2,y_2}-B_{x_2,1}-B_{1,y_1}+B_{x_1-1,y_1-1}

储存

树状数组本质就是一个数组,我们用 C 来表示,然后把 C 排成数🎄的样子,就像前面的那个图那样

C[1]=A[1]C[1]=A[1]
C[2]=A[1]+A[2]C[2]=A[1]+A[2]
C[3]=A[3]C[3]=A[3]
C[4]=A[1]+A[2]+A[3]+A[4]C[4]=A[1]+A[2]+A[3]+A[4]
C[5]=A[5]C[5]=A[5]
C[6]=A[5]+A[6]C[6]=A[5]+A[6]
C[7]=A[7]C[7]=A[7]
C[8]=A[1]+A[2]A[8]C[8]=A[1]+A[2] \cdots A[8]

很明显 C[i]=A[ilowbit(i)+1]+A[ilowbit(i)+2]++A[i]C[i]=A[i-lowbit(i)+1]+A[i-lowbit(i)+2]+ \cdots +A[i]

用代码写就是

for (j=i-lowbit(i)+1; j<= i; j++)
c[i] += a[j];

对于 1, 3, 5, 7 这类 C[i]C[i] 后只有一个 A[i]A[i] 的,我们称之为基点
不难发现基点的都是是奇数,即 lowbit=1
反之,lowbit=1 的数一定是奇数,也一定是基点。

而对于 1, 2, 4, 8 这类 C[i]C[i] 后是 x=1iax\sum_{x=1}^i a_x 的,我们称之为统括点
也不难发现,统括点的二进制能写成 1000…… 的形式
那么统括点一定就是 2 的幂,反之 2 的幂也一定是统括点

特别的,1 既是基点又是统括点
6 不是基点也不是统括点

单点修改

如何进行单点修改,其实在之前已经讲过了
比如我们让 A[3]+1A[3]+1,那么有包含 A[3]A[3] 的所有 CC 都要 +1+1
包括 C[3],C[4],C[8],C[16],C[32]C[3],C[4],C[8],C[16],C[32]\cdots

那么我们只需要这样就行了

for(j=i; j<=n; j+=lowbit(j)) 
C[i] += x;

区间查询

要想得到 i 到 j 的所有数的总和 sumi,jsum_{i,j},只需要得到 sum1,isum_{1,i}sum1,jsum_{1,j}

sumi,j=sum1,isum1,j+Aisum_{i,j} = sum_{1,i} - sum_{1,j} + A_i

也就是前面讲到的前缀和

先求 sum1,isum_{1,i} ,即从 i 开始不断减去 lowbit 并加 C 的值,直到找到第一个统括点(第一个包含该点的统括点)

int find(int x) {
int sum = 0,i;
for(i=x; i!=lowbit(i); i-=lowbit(i))
sum += c[i];
sum += c[i]; //因为最后一次循环并没有进入,故在此处再加一次c[i]
return sum;
}

sum1,jsum_{1,j} 同理

结束

附上 AC 代码

#include <cstdio>
#include <iostream>
using namespace std;

int n,m,k,x,aa;
int a,c[500110];

int lowbit(int x) {
return x & -x;
}
void add(int x,int k) {
while(x<=n) {
c[x] += k;
x += lowbit(x);
}
}
int find(int x) {
int sum = 0,i;
for(i=x;i!=lowbit(i);i-=lowbit(i))
sum += c[i];
sum += c[i];
return sum;
}

int main() {ssd
cin >> n >> m;
for(int i=1;i<=n;i++) {
cin >> a;
add(i,a);
}
while(m--) {
cin >> aa >> x >> k;
if(aa==1) add(x,k);
else cout << find(k) - find(x-1) << endl; //此处和 find(k) - find(x) + a[x] 是一样的
}
return 0;
}


Comments

Unable to load Disqus, please make sure your network can access.