lucifer的网络博客 ·

树状数组，线段树，傻傻分不清楚？

💡 原文中文，约4500字，阅读约需11分钟。

📝

内容提要

树状数组（Fenwick Tree）是一种数据结构，用于高效计算数组的前缀和和区间和。与线段树相比，树状数组需要更少的空间，代码实现简单。树状数组通过二进制拆分区间来计算前缀和，利用lowbit快速求区间和。树状数组的基本操作包括更新元素的值和查询区间和。

🔎

树状数组和线段树都能解决区间问题，但树状数组的空间需求仅为n，而线段树通常需要4n空间。在内存受限的题目中，树状数组可能成为通过的关键。此外，树状数组代码实现更简单，但思想更复杂，需要二进制拆分和lowbit等数学基础。

树状数组通过二进制拆分将前缀和查询转化为多个关键区间的和。例如查询[1,7]时，7的二进制111拆分为长度1、2、4的区间。这些区间的右端点互不相同，恰好对应tree数组的索引。理解这一原理是掌握树状数组的关键。

lowbit(i) = i & -i 用于获取i的二进制中最低位的1对应的值。在树状数组中，lowbit帮助快速定位下一个区间：查询时i -= i & -i，更新时i += i & -i。这一技巧使得树状数组的查询和更新操作都能在O(log n)时间内完成。

树状数组适合处理前缀和、区间和等可合并的区间问题，且代码简洁。但它的思想较难，建议先学习线段树再学习树状数组。对于非竞赛同学，掌握线段树基本足够；若准备竞赛，树状数组是必须掌握的。

❓

树状数组主要用于高效计算数组的前缀和和区间和。

树状数组相比线段树需要更少的空间，代码实现也更简单。

树状数组通过二进制拆分区间来计算前缀和，利用lowbit快速求和。

lowbit用于获取一个数的二进制中最低位的1对应的值，帮助快速求出区间和。

更新树状数组中的元素需要通过更新对应的区间和，使用数学公式进行更新。

树状数组的基本操作包括更新元素的值和查询区间的和。