树状数组

前缀和

犹记前缀和数组：

支持 $O (1)$ 的查询以及 $O (n)$ 的修改。

为什么修改这么慢呢，因为对于 $a_{i}$ ， $s_{1} \sim s_{i}$ 都含有这个信息。

导致查询和修改的耗时太不平衡了

为了平衡，我们给每个前缀和数组不要让他从记录从开头到当前位置的数值。

有一种方法是，每个位置记录 $s [i] = \sum_{l = i - k + 1}^{i} a [i]$

即每个位置记录当前位置到之前 $k$ 个数字的和

每次查询，可以一下得到 $k$ 个位置的和，然后再去之前找，知道不足 $k$ 个时再一个一个加起来

cpp

int l,r;cin>>l>>r;
int sum=0;
while(r-l+1>=k)
{
    sum+=s[r];
    r-=k;
}
for(int i=l;i<=r;++i) sum+=a[i];

这样查询的时间复杂度是 $O (\frac{n}{k} + k)$

修改的时候，因为每个位置只被 $k$ 个 $s [i]$ 记录下来了，所以只用改 $k$ 个位置

cpp

int p,v;
cin>>p>>v;
for(int i=p;i>p-k;--i) s[i]=s[i]-a[p]+v;
a[p]=v;

修改时间复杂度是 $O (k)$

可以证明 $\frac{n}{k} + k \geq 2 \sqrt{n}$ ，当 $k = \sqrt{n}$ 时取最小值，所以平均时间复杂度是 $O (n \sqrt{n})$ 。

既然事已至此，我们不妨把它更形式化一点，每 $\sqrt{n}$ 个元素合成一个块，每个块记录一下元素的总和，此时得到了一种分块算法。

分块不是本节的重点，这个算法可以去分块那一章了解。

有一种更灵活的记录方式，可以将复杂度进一步降低

对于位置 $x$ ，取出它的二进制最低位对应的数字 lowbit(x)

假设 $x = (10100)_{2}$ 则 $l o w b i t (x) = (100)_{2} = 4$

那么 $s [x] = \sum_{x - 4 + 1}^{x} a [i]$

即从储存了 $x$ 开始，往前 $l o w b i t (x)$ 个位置的元素之和。

(图源：oiwiki)

求 $1 \sim r$ 的和，先取 $s u m = s [r]$ 然后令 $r - = l o w b i t (r)$ 就可以干掉一个二进制位。

例如求 $a [1] \sim a [7]$ 的和：

由此得：至多 $l o g_{2} (r)$ 此就可以得到整个前缀的和

cpp

int r;cin>>r;
int sum=0;
while(r) sum+=s[r],r-=lowbit(r)

当需要修改位置 $x$ 上的信息时，要考虑哪些位置的 $s$ 是包含自己的

每个位置的 $s$ 覆盖的范围不会超过自己的 $l o w b i t$ 的范围，而且每个范围大小的 $l o w b i t$ 肯定只有一个包含自己的位置（因为相邻两个lowbit 至少差了 lowbit 个位置）

$x$ 位置本身包含自己，下一个涉及自己的位置是 $> x$ 且 $l o w b i t > l o w b i t (x)$ 的最小的数，即 $x + l o w b i t (x)$

涉及到的位置其实就是图中黑线指向的所有节点

cpp

int x,k;cin>>x>>k;
while(x<=n) s[x]+=k,x+=lowbit(x)

和前缀和意义，如果是查询一个区间 $[l, r]$ ，就让 $[1, r] - [1, l - 1]$ 。

所以它也维护的信息具有可减性，或者说具有逆元。

lowbit

在这里补充说明以下如何快速求 $l o w b i t (x)$ ，即一个数的二进制最低位

计算机中存储负数时用的是补码（这个概念这里不介绍）

因为补码是原本的二进制取反再 $+ 1$ 。

原本 $x$ 低位等于 $0$ 的位，在 $- x$ 的反码中这些位都是 $1$ ，知道遇到一个 $x$ 等于 $1$ 的位。

例如： $x = (10100)_{2}$

那么 $[- x]_{反} = (01011)_{2}$

再给反码 $+ 1$ ，那么就会让 $- x$ 的补码的最低位和 $x$ 的最低位对齐

$[x]_{补} = (10100)_{2}, [- x]_{补} = (01100)$

此时除了最低为，其他位均与 $x$ 不同。

所以 lowbit(x)=x&-x。

例题：

P3374 【模板】树状数组 1 动态前缀和

P3368 【模板】树状数组 2 动态差分

树状数组支持单点修改和区间查询，在这两个功能的基础上可以实现动态前缀和（区间查询）和动态差分（单点修改）

前缀和：查询 $O (1)$ ，修改 $O (n)$

差分：查询 $O (n)$ ，修改 $O (1)$

树状数组可以说是平衡了两者的时间复杂度。

值域

P1908 逆序对

给定一个 $1 \sim n$ 的序列，求其中的逆序对数

根据定义，是要求每个数字前面有多少大于自己的数字

对 $a_{i}$ 来说，就是求 $[a_{i} + 1, n]$ 这个范围内的数字个数

然后每次统计完，再给 $a_{i}$ 位置 $+ 1$

cpp

for(int i=1;i<=n;++i)
{
	ans+=query(n)-query(a[i]);
    update(a[i],1);
}

练习题

P5677 [GZOI2017] 配对统计

P1966 [NOIP2013 提高组] 火柴排队

P1972 [SDOI2009] HH的项链特别重要的题，一定要会

P2345 [USACO04OPEN] MooFest G

P4868 Preprefix sum

树状数组 ​

前缀和 ​

lowbit ​

值域 ​

练习题 ​

树状数组

前缀和

lowbit

值域

练习题