树状数组
1、算法介绍
树状数组的功能：时间都是O（logn）
（1）快速求前缀和
（2）修改某一个数
思路：
将这个数x用二进制表示
然后划分区间，依次分为
每个区间的长度，都是(L,R]中R的最后一位1所对应的次幂。
由lowbit(x)=x&-x可以求出x的最后一位1，则区间可以表示为(R-lowbit(x)+1,R]
设a为原数组
令C(x)=a(R-lowbit(x)+1,R]，为该下标在原数组a对应的区间和。在这里就实现了在O（logn）时间里完成前缀和。
用数据手动模拟一下，不难发现所有的奇数都是它本身(因为最后一位都是1)，2的次方项都是从开头到自己的和。
而且得到每个c(i)最少需要几个数相加也能看出。
添加操作，将x加上k，同时更新与k有关的所有和。
void add(int x, int k)
{
for(int i = x; i <= n; i += lowbit(i))
t[i] += k;
}
查询操作，查询前x数的和，
int ask(int x)
{
int sum = 0;
for(int i = x; i; i -= lowbit(i))
sum += t[i];
return sum;
}
2、板子题——********************
1、思路：
投递字节跳动等公司7个岗位 >
