树状数组(高级数据结构)-蓝桥杯

た入场券 2023-09-24 18:48 78阅读 0赞

# **一、简介** #

*  **树状数组 (Binary Indexed Tree,BIT)，利用数的二进制特征进行检索的一种树状结构。**

*  **一种真正的高级数据结构： 二分思想、二叉树、位运算、前缀和。**

*  **高效!**

*  **代码极其简洁!**

# **二、基本应用** #

*  **数列a1,a2,....,an，操作：**

*  **单点修改：修改元素add(k,x)： 把ak加上x。**

*  **求和：**

**sum (x) = a1 + ... + ax**

**区间和ai + ... + aj = sum(j) - sum(i-1)**

# **三、不修改、只查询** #

*  **数列aj, a2,..., an，求区间和： ai+ ...+aj**

*  **数列是静态的，用前缀和计算区间和，特别高效。**

*  **前缀和：sum\[i\]=a1+...+ ai**

*  **区间和： ai+...+aj = sum\[j\]-sum\[i-1\]**

*  **查询一次区间和，O(1)**

*  **代码**

![59a1b8fdf19c4cfea7633f2f221601ab.png][]

![9753eecaeff844b288e9b37b9aa6961e.png][]

*  **如果数列是动态的**

*  **修改元素add(k,x)：把a加上x。**

**复杂度O(1)**

*  **求区间和：sum(j) - sum(i-1)**

**复杂度：O(n)--------->效率低**

# **四、动态修改、求区间和： 用树状数组** #

*  **数列是动态的**

*  **修改元素add(k,x)：把ak加上x。**

*  **求区间和：sum(j) - sum(i-1)**

*  **复杂度都是： O(logn)**

*  **代码**

![e25ecd8e2a114c369431bf815ca94aee.png][]

# **五、从二叉树到树状数组** #

![306239bc46d04e7b9b55b35aafdd05cc.png][]

# **六、神奇的lowbit(x)操作** #

*  **语法：lowbit(x)=x &-x**

*  **功能：找到x的二进制数的最后一个1**

![b8c005e5f39b40e1b1565644b8789b1d.png][]

# **七、tree\[ \]数组** #

*  **从lowbit(x)推出tree\[ \]数组，所有的计算都基于tree\[ \]，令m =lowbit(x)。**

*  **定义tree\[x\]：把ax和它前面共m个数相加。**

*  **例： lowbit(6)=2，有tree\[6\] = a5+a6。**

![640ebe84b0a74307892485c998d3dbaf.png][]

![628656ba5f6f4a0c921bd17350d9b334.png][]

*  **横线中的黑色表示tree\[x\]，等于横线上元素相加的和。**

![e7ac00622c004d2fa52802f035468265.png][]

# **八、基于tree\[ \]的计算** #

*  **求和sum=a1 +...+ax**

**利用tree\[ \]数组求sum，例如：**

**sum\[8\] = tree\[8\]**

**sum\[7\] = tree\[7\] + tree\[6\] + tree\[4\]**

**sum\[9\] = tree\[9\] + tree\[8\]**

*  **以上关系是如何得到的?借助lowbit(x)。**

# **九、sum\[ \]的计算** #

*  **例： sum\[7\] = tree\[7\] + tree\[6\] + tree\[4\]**

**(1)从7开始，加上tree\[7\]；**

**(2) 7 -lowbit(7)= 6，加上tree\[6\]；**

**(3) 6 - lowbit(6) = 4，加上tree\[4\]；**

**(4) 4-lowbit(4)= 0，结束。**

*  **sum()的复杂度?--------->O(logn)------非常好!**

![b15cd0e6abf8419c98e9a621c5d79482.png][]

# **十、sum\[ \]的更新** #

*  **更改ax，和它相关的tree都会变化。**

*  **例如改变a3，那么tree\[3\]、tree\[4\]、tree\[8\]...都会改变。**

*  **影响哪些tree\[ \]? 仍然利用lowbit(x)**

**(1) 更改tree\[3\]；**

**(2) 3 +lowbit(3)= 4，更改tree\[4\]；**

**(3) 4 +lowbit(4)=8，更改tree\[8\]；**

**(4)直到最后的tree\[n\]。**

*  **复杂度?--------->O(logn)------非常好!**

![b15cd0e6abf8419c98e9a621c5d79482.png][]

[59a1b8fdf19c4cfea7633f2f221601ab.png]: https://img-blog.csdnimg.cn/img_convert/59a1b8fdf19c4cfea7633f2f221601ab.png
[9753eecaeff844b288e9b37b9aa6961e.png]: https://img-blog.csdnimg.cn/img_convert/9753eecaeff844b288e9b37b9aa6961e.png
[e25ecd8e2a114c369431bf815ca94aee.png]: https://img-blog.csdnimg.cn/img_convert/e25ecd8e2a114c369431bf815ca94aee.png
[306239bc46d04e7b9b55b35aafdd05cc.png]: https://img-blog.csdnimg.cn/img_convert/306239bc46d04e7b9b55b35aafdd05cc.png
[b8c005e5f39b40e1b1565644b8789b1d.png]: https://img-blog.csdnimg.cn/img_convert/b8c005e5f39b40e1b1565644b8789b1d.png
[640ebe84b0a74307892485c998d3dbaf.png]: https://img-blog.csdnimg.cn/img_convert/640ebe84b0a74307892485c998d3dbaf.png
[628656ba5f6f4a0c921bd17350d9b334.png]: https://img-blog.csdnimg.cn/img_convert/628656ba5f6f4a0c921bd17350d9b334.png
[e7ac00622c004d2fa52802f035468265.png]: https://img-blog.csdnimg.cn/img_convert/e7ac00622c004d2fa52802f035468265.png
[b15cd0e6abf8419c98e9a621c5d79482.png]: https://img-blog.csdnimg.cn/img_convert/b15cd0e6abf8419c98e9a621c5d79482.png