树状数组

0x01 引入

两道例题
相信大家首先想到的便是朴素的暴力，但T1 查询O(n^3) 与T2 修改O(mn) 的数据让人头疼。
之后想到的便是前缀和维护，但无奈修改的操作提高了复杂度
于是便引入了线段树树状数组！

0x02 定义

树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。——某度百科

0x03 原理

介绍一个操作：lowbit。作用是获得一个数二进制下最低位的1所代表的数值
代码实现
inline int lowbit(int a){return a&-a;}
作用：实现一个如下图的数据结构

于是，操作一个节点时只需要操作与他有上下级关系的节点就OK啦

另外两个经常使用的函数：
int sum(int i){int ret=0;while(i>0){ret+=C[i];i-=lowbit(i);}return ret;}
void update(int i,int val){while(i<=n){C[i]+=val;i+=lowbit(i);}}

0x04 优缺点

优点：代码短小 实现简单 容易扩展到高纬度的数据

缺点：只能用于求和 不能求最大/小值 不能动态插入 数据多时 空间压力大

本文部分参考这里