树状数组
目的
是为了优化数组、前缀和数组，因为这两个数组有如下特点：
数组：
- 单点修改：O(1)
- 区间查询： O(n)
前缀和数组：
- 单点修改： O(n)
- 区间查询：O(1)
而当需要同时进行这两种操作的时候，时间复杂度其实是取决于最坏的情况，即O(n)。
此时需要一种数据结构，能综合一下这两种数组的优点，使不那么的极端，树状数组就诞生了。
树状数组：
- 单点修改：O(log n)
- 区间查询：O(log n)
原理
首先，分析一下为什么数组、前缀和数组会出现极端的情况。其实数组相当于是划分为了[i,i]这样的n个区间，这有利于单点修改。而前缀和数组是划分为了(0,i)这样的n个区间，这有利于区间查询。
而树状数组是利用二进制进行了一种新的区间划分（树状数组的英文名是BIT，二进制下标树），使区间划分的较为匀称，这样均衡了其在单点修改与区间查询之间的能力。
引入几个概念：
- C(i)：区间(i - lowbit(i),i]，以i结尾，长度为lowbit(i)的区间的区间和
- lowbit(i)：i的二进制表示中最后一个1及其之后的0（...100000），lowbit(i)可以使用 i & -i轻易求出
- sum(x)求法：将x划分出的区间进行累和
- add(x,c)：将x节点与其父节点都加c，即包含x的区间都加c
其实主要就是一个区间划分，然后在修改的时候，是要向上找父节点，不断对父节点进行更新，找负节点的方法是+lowbit(i)。在查找的时候，是要向下找子区间，不断的对子区间进行累和，找子区间的方法是-lowbit(i)。
代码模板
const int N = 5e5+5;
int n;
int tr[N],a[N];
int lowbit(int x){
return x & -x;
}
void add(int x,int c){
for(int i = x;i <= n;i += lowbit(i)) tr[i] += c;
}
int sum(int x){
int ans = 0;
for(int i = x;i;i -= lowbit(i)) ans += tr[i];
return ans;
}
int query(int l,int r){
return sum(r) - sum(l-1);
}