P3368 【模板】树状数组 1 DRAFT

Posted March 18. 2020. 1663 words. 8 min read.

题目

题目描述

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

将某一个数加上 $x$
求出某区间每一个数的和

输入格式

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

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 33 个整数，表示一个操作，具体如下：

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

输出格式

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

输入输出样例

输入 #1

输出 #1

14
16

说明/提示

【数据范围】

对于 $30\%$ 的数据， $1 \le n \le 8，1\le m \le 10$ ；

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

对于 $100\%$ 的数据， $1\le n,m \le 5\times 10^5$ 。

样例说明：

故输出结果 14、16

数据范围

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

题解

树状数组

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

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

特点

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

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

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

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

前置知识

lowbit

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

树状数组结构

十进制	二进制
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001
10	1010

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

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

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

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

再把 lowbit 说简单点就是

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

玄学公式登场 x & -x

举个例子

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

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

为什么要这样干呢

我们先列出 1~8 的 $lowbit$

$1\;2\;1\;4\;1\;2\;1\;8$

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

对应管理

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

前缀和

一维前缀和

现有一个长度为 $N$ 的序列 $A$ ，需要进行 $M$ 次操作，每次操作选取从 $A_i$ 到 $A_j$ 共 $j-i+1$ 个数并求出他们的总和（N 和 M 可以很大）

例：

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

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

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

那我们可以新建一个数组 $B$ ，其中 $B_i=B_{i-1} +A_i$

此时我们需要求 $a_i-a_j$ 的总和，~~意会下~~，只需要求 $B_j-B_{i-1}$ 就好啦

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

二维前缀和

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

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]

若我们要求 $x_1,\,y_1$ 与 $x_2,\,y_2$ 两点所围成矩形内数字的和公式 $sum=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[2]=A[1]+A[2]$
$C[3]=A[3]$
$C[4]=A[1]+A[2]+A[3]+A[4]$
$C[5]=A[5]$
$C[6]=A[5]+A[6]$
$C[7]=A[7]$
$C[8]=A[1]+A[2] \cdots A[8]$

很明显 $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]$ 后只有一个 $A[i]$ 的，我们称之为基点
不难发现基点的都是是奇数，即 lowbit=1 反之，lowbit=1 的数一定是奇数，也一定是基点。

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

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

单点修改

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

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

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

区间查询

要想得到 i 到 j 的所有数的总和 $sum_{i,j}$ ，只需要得到 $sum_{1,i}$ 和 $sum_{1,j}$

sum_{i,j} = sum_{1,i} - sum_{1,j} + A_i

也就是前面讲到的前缀和

先求 $sum_{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;
}

$sum_{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;
}