数据结构: 树状数组

本文主要是介绍数据结构: 树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在OI赛事中，数据结构是非常重要的一个内容，更是有人说过，算法+数据结构=程序:
$Algorithm+Data$ $Structure=Programming$
接下来，我们就来介绍一些经典重要的数据结构。
首先是树状数组。

实际上，数据结构就相当于一种算法，是在某种结构上实现某算法。
树状数组是一个查询和修改复杂度都为 $O(lo{g}_{2}n)$ 的数据结构，运用树状数组可以实现很多算法问题，

比如单点修改，区间求和，求逆序对等等。
比如区间求和，若 $n$ 为数列长度，$m$ 为查询次数，那么普通查询总和的最坏时间复杂度为 $O(nm)$，假设 $n$ 和 $m$ $<=$ $10^5$，时间复杂度就接受不了了，所以很多数据结构比如树状数组，RMQ问题的ST，线段树以及倍增(不太算是数据结构，偏向于 $Algorithm$)之类的，多数情况下都是为了压缩时间复杂度，尽量达到 $O(10^5-10^7)$左右，使程序能在 $1s$ 的时间内求解。
而树状数组的代码效率远远高于线段树，树状数组代码比较少，但线段树代码量特别大

基本思想:

根据任意正整数关于 $2$ 的不重复次幂的唯一分解性质，若一个正整数 $x$ 的二进制表示为 $10101_{(2)}$，其中 $1$ 的位是 $0,2,4$ ，则 $x$ 可以被“二进制分解”成 $2^4+2^2+2^0$，进一步，区间 $[1,x]$，可以分成 $lo{g}_{2}x$个小区间:

1. 长度为 $2^4$ 的小区间 $[1,2^4]$
2. 长度为 $2^2$ 的小区间 $[2^4+1,2^4+2^2]$
3. 长度为 $1$ 的小区间$[2^4+2^2+1,2^4+2^2+1]$

树状数组就是基于上述思想的数据结构，基本作用是维护序列的前缀和。
对于区间 $[1,x]$，树状数组将其分为 $lo{g}_{2}x$ 个小区间，$lo{g}_{2}x$ 个子区间的累加和就是 $[1,x]$ 的区间和。

基本算法:

由上文可知，这些子区间的共同特点是，若区间结尾为 $R$，则区间长度就等于 $R$ 的“二进制分解”下最小的 $2$ 的次幂，我们设为 $lowbit(R)$
$lowbit$的计算很简单，$lowbit(n)=n$ & $(-n)$，表示 $n$在二进制表示下最低位的 $1$ 以及后面的 $0$ 构成的数。如$lowbit(101100_{(2)})=100_{(2)}=4_{(10)}$
我们就可以写一个子程序函数 $lowbit$ 来实现:

int lowbit(int x) {return x&(-x);
}

对于序列 $A$，我们建立一个数组 $C$，其中 $C$ $[x]$ 保存序列 $A$ 的区间 $[x-lowbit(x)+1,x]$ 中所有数之和。

我们构造上图所示的结构，满足以下性质:

1. $C$ $[x]$ 等于以 $x$ 为根的子树中所有叶节点的和。
2. $C$ $[x]$ 的叶节点个数等于 $lowbit(x)$。
3. $C$ $[x]$ 的父亲节点是 $C$ $[x+lowbit(x)]$。
4. 深度为 $lo{g}_{2}N$
   如图我们可以知道:
   $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]$ + $A[3]$ + $A[4]$ + $A[5]$ + $A[6]$ + $A[7]$ + $A[8]$

对某个单点的元素进行修改

就先讲加法操作
树状数组支持单点加法操作，根据树状数组的结构特性，节点 $x$ 及其所有祖先节点的 $C$ 值会受到操作的影响，而任意一个节点的祖先最多有 $lo{g}_{2}N$ 个，逐一对 $C$ 值进行加法就行了。时间复杂度为 $O(lo{g}_{2}N)$。
Code:

void update(int x,int y) {  //将第x个数加上yfor(;x<=N;x+=lowbit(x))  c[x]+=y;
}

而要将某个单点的元素直接改成 $y$，则需要如下代码:

void update(int x,int y) {  //将第x个数改成yfor(int i=x;i<=N;i+=lowbit(i))  c[i]+=(y-a[i]);
}

查询前缀和

树状数组支持查询前缀和，较为简单，时间复杂度为 $O(lo{w}_{2}N)$ 直接给出
Code:

long long ask_sum(int x) {  //函数名各式各样//查询前x个数的和long long ans=0;for(;x;x-=lowbit(x))  ans+=c[x];return ans;
}

接下来，我们用一道简单的例题来详细讲解一下树状数组

例题

单点修改区间查询

[题目描述]

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

1. 将某个数加上 $x$；
2. 求出某区间所有数的和。

输入格式

第一行两个整数 $n,m$， 分别表示该数列长度和操作个数
第二行 $n$ 个整数，表示原数列。
接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下:
第一个整数为opt，有下列两种输入情况
1 x k: 将第 $x$ 个数加上 $k$
2 x y: 询问区间 $[x,y]$ 所有数的和
输出格式
对于每个opt=2，输出一行一个整数，表示相应的结果。

数据范围

$1$ $<=$ $n,m$ $<=$ $10^6,$ $0$ $<=$ $|a[i]|,x$ $<=$ $10^6$

树状数组模板题，只是操作2不是求前缀和，是某个区间 $[x,y]$ 的和，我们用 $ask\_sum(y)-ask\_sum(x-1)$ 就可以了。
Code:

#include<bits/stdc++.h>
int n,q,opt;
long long a[10000001],c[10000001];
long long x,y;
inline int lowbit(int x) {  //lowbit函数return x&(-x);
}
inline void update(int x,long long k) {for(;x<=n;x+=lowbit(x))  c[x]+=k;
}
inline long long ask_sum(int x) {long long ans=0;for(;x;x-=lowbit(x))  ans+=c[x];return ans;
}
int main() {std::cin>>n>>q;for(int i=1;i<=n;i++)  scanf("%lld",a+i),update(i,a[i]);  //输入while(q--) {scanf("%d %lld %lld",&opt,&x,&y);switch(opt) {case 1:  //当opt=1时将某个单点元素加上yupdate(x,y); break;case 2:  //当等于2时查询某个区间所有数的和printf("%lld\n",ask_sum((int)y)-ask_sum((int)x-1)); break;}}
}

树状数组的模板是非常重要的，虽然说理解也很重要，但在背诵的同时理解的效率会更高。
这篇介绍树状数组的文章到此结束了，如有bug请指出，不胜感激！
下一篇数据结构的文章介绍线段树

这篇关于数据结构: 树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---