2018.1.292018.2.2树状数组学习笔记（带各种应用）大本营

树状数组是大家很熟悉的数据结构了吧！不明白的话自己手动学习。作者要好好复习树状数组了。

ps：点击每道题目名称可跳转至题目网页。

easy（简单模板）：

简单单点加法+求和操作。

#include#include#include#include#include#defineLLlonglong#definemaxn500001usingnamespacestd;inlineintread(){intx=0;boolf=1;charch=getchar();while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}if(f)returnx;return0-x;}intn,m;inttree[maxn<<1];intlowbit(intx){returnx&-x;}voidadd(intx,intk){for(inti=x;i<=n;i+=lowbit(i))tree[i]+=k;}intsum(intx){intres=0;for(inti=x;i>0;i-=lowbit(i))res+=tree[i];returnres;}intmain(){n=read(),m=read();inti,x,y,p;for(i=1;i<=n;i++)add(i,read());for(i=1;i<=m;i++){p=read(),x=read(),y=read();if(p==1)add(x,y);elseprintf("%d\n",sum(y)-sum(x-1));}return0;}

这题跟下面一题类似，因此略。

简单区间加法+求和操作。

这题用线段树的做法当然是废话，但树状数组的做法需要应用一点数学知识：差分。

额，以前写过注释了，现在直接贴上来。

medium（小试牛刀）：

额，我真想吐槽一下用归并排序写逆序对的常数真是大到爆炸，于是来一发树状数组吧。

思路：将给的n个数分别捆绑上它们在原序列的位置（可以用struct捆），然后将这些数从大到小排序，从大到小（重点！）依次将每个数的值离散化，然后按照原序列从前往后的顺序将每个数离散化后的值插入树状数组的对应位置。

离散化是因为输入的数有可能很大（10^9？），数组开不下那么多位，而最多只有4W个数，因此离散化后就只需要给树状数组开4W位了。

不难证明其正确性——树状数组中对第x位的查询求的是第1-x位的和，由于是按照原序列从前往后的顺序插入值，先插入树状数组的值的位置一定在后插入树状数组的值的位置的前面。如果先插入的数比后插入的数大，那这两个数就能组成逆序对了。

有人可能会问：树状数组查询的是前缀和，也就是之前插入的比当前数小的数的个数，怎么能查询出比当前数大的数的个数呢？

呃，你是不是没明白上面红字标的那句话？“从大到小依次将每个数的值离散化”这句话的实际操作看这个例子（108644的每位不是离散化成43211，而是12344）。

这样原序列就变成了反序的，这时树状数组看似查询的是之前插入的比当前数小的数的个数，实际上之前那些“比当前数小的数”都是在反序离散化后形成的，它们原本的值是比当前数大的。再加上那些数的位置在当前数前面，那些数就都能和当前数组成逆序对了。

因此对于每一个后插入的数，设这个数在原序列是第x位，求一下树状数组中第1~x位的和（简单query操作）即可求出所有位置在这个数（第x位）前面且原数比当前数在原序列中的数大的数的数量了。最后总数量就是原序列的总逆序对数。

另外，上面只是理论可行的做法，实际上逆序对的定义是iaj（不是ai>=aj），而对于每一个插入的数，树状数组的query操作求得是第1~x位的和，算上了之前插入的等于当前这个数的数，为了把它们去掉，实际查询的时候可以让query只求第1~x-1位的和，这样即可避免将两个相同的数算为逆序对。

当然如果您有强迫症，您可以查询第1~x位的和，只不过要多写两行代码把那些相同的数多查询出的答案减掉。

#include#include#includeusingnamespacestd;intn,tot,tree[100010],d[100010];longlongans;structnode{intval,id;booloperator<(constnode&a)const{returnval>a.val;}}a[100010];intlowbit(intx){returnx&-x;}voidadd(into,intx){for(;o<=n;o+=lowbit(o))tree[o]+=x;}intquery(intx){intsum=0;for(;x>0;x-=lowbit(x))sum+=tree[x];returnsum;}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++){scanf("%d",&a[i].val);a[i].id=i;}sort(a+1,a+n+1);//离散化d[a[1].id]=++tot;for(inti=2;i<=n;i++){if(a[i].val!=a[i-1].val)++tot;//要设相同的数在同一位置d[a[i].id]=tot;}for(inti=1;i<=n;i++){add(d[i],1);ans+=query(d[i]-1);}printf("%lld",ans);return0;}

2.弱点

这道题所在的oj要花钱才能注册账号看题……因此我贴题目吧。

一队勇士正在向你进攻，每名勇士都有一个战斗值ai。但是这队勇士却有一个致命弱点，如果存在iaj>ak，则会影响他们整体的战斗力。我们将这样的一组(i,j,k)称为这队勇士的一个弱点。请求出这队勇士的弱点数目。

输入的第一行是一个整数n，表示勇士的数目。

接下来一行包括n个整数，表示每个勇士的战斗值ai。

输出为一行，包含一个整数。表示这队勇士的弱点数目。

410831SampleOutput4HINT对于30%的数据，3<=n<=100

对于100%的数据，3<=n<=1000000

三维逆序对，很明显跟上一题做法相似。那怎么搬运呢？我们可以基于三维逆序对的中间元素考虑。

思路：既然能用树状数组求第x个数能和第1~x-1个数组成多少逆序对，那肯定也能求第x个数能和第x+1~n个数组成多少逆序对，不过由于树状数组只能用来求前缀和，因此我们可以把后者理解为求第x个数能和第x+1~n个数组成多少反向同序对（大家都理解同序对吧？逆序对的反义词，即满足ij且ai

tip：我写代码的时候为了省事，依然做了从大到小和从小到大的离散化（从小到大的离散化），实际上这道题题面标明了ai不会超过10^6，数组开得下，而且每个ai互不相同，这说明离散化的去重效果就没用了，因此完全可以不用离散化，反序嘛直接把1000001-ai的值插入树状数组就行了。

这题明显可以用树状数组打。

思路：

由于每个数可能很大，数组开不下，我们依然把所有数离散化，不过这不是逆序对，要从小到大离散化。树状数组tree[i]表示离散化后的数i为当前第几小数，将对于每个数x，对树状数组第x位进行add操作+1即可，表示它占了一个排名，这样比x大的数都要往后排一名。

比如序列：53791

离散化后：32451

插入第1个数3后，第i位对应的query(i)：00111（query(i)操作在逆序对题中已经讲过，表示求树状数组第1~i位的和）

插入第2个数2后，第i位对应的query(i)：01222

插入第3个数4后，第i位对应的query(i)：01233

插入第4个数5后，第i位对应的query(i)：01234

插入第5个数1后，第i位对应的query(i)：12345

相信大家都知道初始序列中的数离散化后的排名是不变的，因此离散化后的数第几小，在原序列中对应的数也是第几小。因此这样做肯定是可行的。

还有一个小问题：怎么查询？

相信大家都注意到query(i)序列是单调不下降的，因此可以使用二分快速查找。那查找几呢？根据题目，我们要求前1，3，5，……个数的中位数。假设我们要求前i个数的中位数，根据求和公式，第(i+1)/2小的数就是中位数。所以只要寻找最小的id使query(id)=(i+1)/2就行了。这个位置id表示的其实是原序列一个数离散化后的数，因此我们把它对应回去，输出它原来的数就行咯。

ps：这题方法太多了，有兴趣了解更简单方法的可以看我写的另一篇随笔。