树状数组，用log(n)的时间解决求前缀和和将a[x]加上一个数。能用树状数组做，当且仅当能够将问题转换为以上两个操作。
树状数组总结
1、修改一个数
void add(int x,int y) { while(x<=n)//在树上所包含的所有集合 { tree[x]+=y; x+=lowbit(x); } } 2、求前缀和
int get(int x) { int sum=0; while(x)//把一条链分成几段加起来 { sum+=tree[x]; x-=lowbit(x); } return sum; } 树状数组变形
1、求逆序对
for(int i=1;i<=n;i--) { s[i]=i-1-get(a[i]);//比a[i]小的，用总的减小的，别忘记减掉自己的1 add(a[i],1); } 2、二维树状数组
void add(int x,int y,int z) { while(x<=n) { int i=y; while(i<=m) { tree[x][i]+=z; i+=lower(i); } x+=lower(x); } } int get(int x,int y) { int sum=0; while(x>0) { int i=y; while(i>0) { sum+=tree[x][i]; i-=lower(i); } x-=lower(x); } return sum; }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
