树状数组的笔记√（hzwer blog）

2022-12-20 15:10:33

 int lowbit(int x)

 {

      return x&(-x);

 }

lowbit（）的返回值就是 2^k 次方的值。

求数组的和的算法：

（1）首先，令sum=0，转向第二步；

（2）接下来判断，如果 n>0 的话，就令sum=sum+cn转向第三步，否则的话，终止算法，返回 sum 的值；

（3）n=n – lowbit（n）（将n的二进制表示的最后一个零删掉），回第二步。

 int Sum(int n)

 {

     int sum=;

     while(n>)

     {

          sum+=c[n];

          n=n-lowbit(n);

     }

     return sum;

 }

求数组的和的算法

当数组中的元素有变更时，树状数组就发挥它的优势了，算法如下（修改为给某个节点 i 加上 x ）：

（1）当 i<=n 时，执行下一步；否则的话，算法结束;

（2）ci=ci+x ，i=i+lowbit（i）（在 i 的二进制表示的最后加零），返回第一步。

代码实现：

 void update(int i,int x)

 {

      while(i<=n)

      {

           c[i]=c[i]+x;

           i=i+lowbit(i);

      }

 }

给某个节点 i 加上 x

http://hzwer.com/914.html

码农公寓