树状数组：
1、树状数组，又称为二进制索引书（binary indexed Trees），通过二进制划分区间；
2、树状数组引入了分组管理制度,管理数组 c[],c[i]表示每个节点可以管理几个节点；
如图：c[4]管理 a[1~4];就是因为c[] 是树状的，所以称此为树状数组
image.png
1、区间长度：其实就是)
如果i的二进制表示末尾有个连续0，那么c[i] 的区间长度为
从a[i]向前个元素 即：
int lowbit(i){
return (-i) & i;
}
2、前驱和后继 概念：
-
直接前驱： c[i]的直接前驱
c[i - lowbit(i)], 即c[i]左侧紧邻的子树的跟 -
直接后驱：c[i]的直接后驱
c[i + lowbit(i)],即c[i]的父节点 - 前驱：c[i]左侧的所有的子树的根
- 后驱：c[i]的所有的祖先
3、前缀和：所有的前驱的节点之和
前i个元素的前缀和---i的所有的前驱节点之和
sum[4] = c[4]
-- 4没有前驱
sum[7] = c[7] + c[6] + c[4]
sum[9] = c[9] + c[8]
//1、求前缀和---持续找前驱
int sum(int x){
int sum=0;
for(int i = x;i != 0;i -= lowbit(i))
sum += t[i];
return sum;
}
4、点更新 ---持续找后继
如果对a[i]更新，那么更新它的所有的祖宗；
/ /2、点更新
static void add(int x,int k){
for(int i = x; i <= n;i += lowbit(i))
t[i] += k;
}
5、查询区间和
如果要求区间和 就是前j个的前缀和减去前i -1个元素的前缀和
即：
+
把1~j分为两段；
int sum(int i, int j){
return sum[j] - sum[i - 1];
}
例题：
https://leetcode.cn/problems/range-sum-query-mutable/
https://www.acwing.com/problem/content/description/243/
