树状数组浅析

前言：

树状数组作为一种码量比线段树少，时间比线段树短，空间比线段树小的算法，是我们所值得学会的。

但值得注意的是，树状数组不能用于区间修改（当然你可以转成单点一个个改）、寻找区间最小值以及最大值一类的问题。

正文：

先转(dao)载(lai)一张图。

如图，显然可得：
c1=a1

c2=a1+a2

c3=a3

c4=a1+a2+a3+a4

c5=a5

c6=a5+a6

c7=a7

c8=a1+a2+a3+a4+a5+a6+a7+a8

c9=a9

可以发现树状数组利用了二分的思想。

我们先定义一个two(x)表示把十进制x转为二进制，保留从后数起的第一个“1”以及它后面的零，再转为十进制。

我们知道一个正数的相反数的二进制等于正数的二进制取反加一。

two(x)=x&(-x)，可以自己举例理解。

那么我们的cx表示的a[x-two(x)+1~x]的和（可视要求什么改为其它）。

如果我们要修改ax，包含ax的ci有哪些呢？

可以发现有c[x]，c[x+two(x)]，c[x+two(x)+two(t+two(x))]， 以此类推。

不信自己举例，很神奇，对不对？

如果我们要求1~x的和。

按照c的定义，ans=c[x]+c[x-two[x]]+.... 以此类推。

如果我们要求l~r的和，可以先求1~r的和，再减去1~l-1的和。

就这些了吧。