树状数组

推导：

已知一个数为

设其二进制表示为：

其中有

所以这个数可以划分为以下几个区间：




我们已知以下条件：

表示二进制表示的最后一位

表示二进制表示的倒数第二位，以此类推

所以对于以上区间中的任意区间，都有长度一定是的二进制表示的最后一位所对应的次幂

所以

即

例子：

的二进制表示为

所以的二进制表示为

根据前面的划分原则，可以划分为

图解：

此为以每一个数为时的区间

基本操作：

1.add( p , v )

：在点 上加上 / 找寻点的所有祖宗节点

理论依据：

设节点的二进制表示为

由内容可知，在对点进行修改时，需要将所有位于其上的区间进行修改，即对其所有祖先进行修改

由中的划分部分可知，将的父节点的二进制表示为

所以，的父节点为，依次进行此操作至根节点即可实现

此定理可以推广至所有节点

运用此定理在该节点和所有祖宗节点上加上修改值即可找寻点的所有祖宗节点

通用代码：

void add(int p,int v)
{
    for(int i=p;i<=n;i+=lowbit(i)) tr[i]+=v;
}

2.sum( x )

：求取前项的和 / 寻找点的所有子节点

理论依据：

已知 :

设节点的二进制表示为

由内容可知，在对点进行修改时，需要将所有位于其上的区间进行修改，即对其所有祖先进行修改

由中的划分部分可知，将的父节点的二进制表示为

所以，的父节点为

此定理可以推广至所有节点

此定理的逆定理即可实现寻找点的所有子节点

由图可知，任意一个区间(即图中节点)都是其所有子节点的和(与根节点用红色线相连)，找出节点的所有子节点后进行相加即可求得前项的和

区间的和可用已求得的区间前缀和之间相减，与普通的前缀和相似

通用代码：

int sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}