习题

首先：

要说树状数组，就必须要说 $\operatorname{lowbit}$。

那 $\operatorname{lowbit}$ 是什么呢？

是一个数的二进制从右往左第一个 $1$ 的值。

例如，$\operatorname{lowbit}(14)$ 是 $2$，$\operatorname{lowbit}(16)$ 是 $16$。

那应该怎么求呢？

是 $n \And (-n)$，众所周知 $-n$ 是 $n$ 的补码，就是 $n$ 按位取反再加 $1$。

神奇的是，$n$ 这样一取反前面的 $0$ 都成 $1$ 了，再加一，$1$ 又变成 $0$ 了，但取反后第一个 $0$ 就成 $1$ 了，竟跟取反前一模一样！

这样一来，只要第一个 $1$ 剩下来了。

我们在举个栗子：

$6$ 的二进制是 $110$，补码是 $010$，$\operatorname{lowbit}(6)$ 就是 $2$。

$24$ 的二进制是 $11000$，补码是 $01000$，$\operatorname{lowbit}(6)$ 就是 $8$。

之后（进入正题）：

我们有一个数列（随便写的）：

$$a{8}={1,1,4,3,7,9,2,5}$$

再写一个表，每个数为下面的两数之和：

32

9 23

2 7 16 7

1 1 4 3 7 9 2 5

我们要实现的是：

  1. 单点修改。
  2. 询问区间。

但我们可以做出优化：

我们发现，如下的点会被用过

32

9

2 16

1 4 7 2

标号：

$~~~~~~~~~~~~~~~~~~~t_8$

32

$~~~~~~~~~t_4$

9

$t_2~~~~~~~~~~~~~t_6$

2 16

$t_1t_3t_5~~~~~~t_7$

1 4 7 2

显然：若 $i$ 为奇数，$t_i$ 等于 $a_i$。

观察可得 $t_i=a_i+a_{i+1}+…+a_{\operatorname{lowbit}(i)+i-1}$。

所以每次跳过 $\operatorname{lowbit}(i)$ 即可。

建树：

每次都把包含 $x$ 的区间（即每次跳过 $\operatorname{lowbit}(x)$）加上 $k$。

1
2
3
void add(int x,int k){
    while(x<=n) t[x]+=k,x+=lb(x);
}

查询：

与上面同理。

1
2
3
4
5
int sum(int x){
    int ans=0;
    while(x) ans+=t[x],x-=lb(x);
    return ans;
}

码字不易，求赞