树状数组

最近花了两天时间学了下树状数组，然后感觉堪比玄学，故写篇文章总结一下。 2024.08.07 UPD：添加了树状数组的树形结构解释，与树状数组上二分。 树状数组（binary indexed tree），也叫BIT，又以其发明人名字被称为Fenwick树。树状数组利用二进制下标来维护区间和，能够做到以log⁡n\log{n}logn的复杂度进行单点修改和区间求和，同时配合差分数组等结构，还能做到区间修改、单点查询和区间修改、区间查询等功能，相比与线段树来说更为简单和优雅。 基本知识 树状数组最为重要的一个设定就是lowbitlowbitlowbit——二进制最低位的1及其后面的0所组成的数字，相比与前缀和，树状数组的每一位维护的是(i−lowbit(i),i]\left(i-lowbit(i),i\right](i−lowbit(i),i]的区间和，比如6，二进制为110，那么这一位维护的就是原数组6到4100的区间和（不包含4）。 那么要如何计算一个数的lowbitlowbitlowbit呢？如果用一个1作为check来判断每一位是否是1，那么代码大概长这样： 1234for(in ...