树状数组
树状数组是一种高效的数据结构，能够解决数量级较大的区间求和问题、区间求最值问题、区间修改、查询问题以及求逆序对等应用。其时间复杂度为 O(log2n)，远远快于线性时间 O(n)。
树状数组的用途：
* 区间求和：树状数组可以快速地计算区间的和，时间复杂度为 O(log2n)。
* 区间求最值：树状数组可以快速地计算区间的最值，时间复杂度为 O(log2n)。
* 区间修改：树状数组可以快速地修改区间的值，时间复杂度为 O(log2n)。
* 区间查询：树状数组可以快速地查询区间的值，时间复杂度为 O(log2n)。
* 求逆序对：树状数组可以快速地计算逆序对的数量，时间复杂度为 O(log2n)。
树状数组的原理：
树状数组的原理是基于二分思想的。我们可以将数组分成多个小块，每个小块的和可以快速地计算出来，然后将这些小块的和相加得到总和。这种方法可以将时间复杂度从 O(n) 降低到 O(log2n)。
创建树状数组：
创建树状数组需要使用 lowbit 函数来将当前项的数加入到后面的每一个需要用到的数组中。lowbit 函数的定义为 k&(-k)，它可以快速地计算出当前项的最低位。
add 函数的实现：
void add(int x,int y) //将 y 加入到 x 中
{
while(x<=10){
C[x]+=y;
x+=lowbit(x);
}
}
read 函数的实现：
int read(int x)
{
int ans=0;
while(x){
ans+=C[x];
x-=lowbit(x);
}
return ans;
}
区间求和：
树状数组可以快速地计算区间的和，时间复杂度为 O(log2n)。我们可以使用 read 函数来计算区间的和。
int read(int x)
{
int ans=0;
while(x){
ans+=C[x];
x-=lowbit(x);
}
return ans;
}
区间修改：
树状数组可以快速地修改区间的值，时间复杂度为 O(log2n)。我们可以使用 updata 函数来修改区间的值。
void updata(long long *c,long long x,long long y) //在数组 c 中后 x 加入 y
{
while(x<=n){
c[x]+=y;
x+=lowbit(x);
}
}
差分数组：
差分数组是一种特殊的树状数组，可以快速地计算区间的和和差异。我们可以使用 Sigma 函数来计算数组中 1 到 x 的和。
long long Sigma(long long *arra,long long x) //数组中 1 到 x 的和
{
long long ans=0;
while(x){
ans+=arra[x];
x-=lowbit(x);
}
return ans;
}
树状数组是一种高效的数据结构，能够快速地解决各种问题，包括区间求和、区间求最值、区间修改、查询问题等。
