这是第四篇树状数组了。。 我们之前讲过树状数组的以下几大作用：
单点加区间查 不会的话-> http://blog.csdn.net/enzymii/article/details/54952957区间加单点查 不会的话-> http://blog.csdn.net/enzymii/article/details/54965280区间加区间查 不会的话-> http://blog.csdn.net/enzymii/article/details/55106863然而上面的会不会的无所谓啊。。。 因为上面我们查的都是区间和性质的东西。。（就是用前缀和差分能减出来的东西_ (:з」∠) _）
而我们今天要做的，是：
在这里，我要给大家讲一下时间复杂度，不过你们要答应我我说完不要走 我们拿能干查询最大值的两样其他东西来比，线段树和rmq.. 用树状数组实现这个功能时，（又要画丑陋的表格）
| 种类 | 线段树 | 树状数组 | rmq |
|---|---|---|---|
| 初始化 | nlogn | < nlogn | nlogn |
| 查询 | logn | logn | 1 |
| 修改 | 单点&区间logn | 单点< logn*logn | 无法修改 |
| 上手难度 | 稍复杂 | 较简单 | 简单 |
| 常数 | 大(没说你 zkw) | 小 | 小 |
| 码长 | 稍长 | 短 | 不长 |
话说这么一比，树状数组究竟优势在哪呢 然后因为lowbit的缘故时间复杂度会玄学很多。。看脸和数据了。。欧洲人民发来贺电 无所谓了。。(⊙v⊙)嗯就是这样。。 我说过（吗？）之前讲的功能都可以不会。。 但我们还是要有一些知识储备的……比如……树状数组优美的、精巧的划分区间的方式。。 各位大拿还记得小角落里的lowbit么~ 树状数组中第i个点所记录的，是[i-lowbit(i)+1,i]的这lowbit(i)个数的信息。我们既然要查询的是最大值，自然这个数组中维护的就是我们最可爱的最大值咯~~ 说人话：树状数组上的c[i]表示a[i-lowbit(i)+1]..a[i]范围内的最大值..
然后查询起来的代码似乎就像这样：
int ask(int l,int r){ int ans=a[r]; while(1){ ans=max(ans,a[r]); if(l==r) break; for(r--;r-lb(r)>=l;r-=lb(r)) ans=max(ans,c[r]); } return ans; }也可以看出来，其实真正的循环次数很少的……（logn也就是个上界，松的很……）
修改起来看上去慢一点，按照这种优美的划分区间的方式，修改我们要这么写（注意是把点x 改为 s）
void update(int x,int s){ a[x]=s; for(;x<=n;x+=lb(x)){ c[x]=s; for(int i=1;i<lb(x);i<<=1) c[x]=max(c[x],c[x-i]); } }这里看来，上界确实要到logn*logn的样子？ 但是，内层循环只需要循环到lowbit(i).. （也就是说当n是奇数的时候是O(1)的（逃~）） 然后，就到了我们的建树。。（蛤？建树不是加点就行了么..） 喂~这里的修改挺慢的啊~ 我们有< nlogn的建树方式呢，为什么不用呢= = 建树的代码：
这样的话功能就讲完了，大家要想练练手的话我们有hdu1754.. 题目传送门在这里：http://acm.hdu.edu.cn/showPRoblem.php?pid=1754（hdu的中文题目..）
最后附对于此题，本蒟蒻弱智的模板：
#include <cstdio>#include <cstring>#define gc getchar()const int INF=~0U>>1;class Binary_Tree4{private: static const int N=0x186AF<<1; int a[N],c[N],n; inline int lb(int x){ return x&-x; } inline int max(const int &a,const int &b){ if(a<b) return b; return a; } inline int min(const int &a,const int &b){ if(a<b) return a; return b; } inline int gnum(){ int a=0;char c=gc;bool f=0; for(;(c<'0'||c>'9')&&c!='-'&&c!='U'&&c!='Q';c=gc); if(c=='-') f=1,c=gc; if(c=='U') return -21; if(c=='Q') return -17; for(;c>='0'&&c<='9';c=gc) a=(a<<1)+(a<<3)+c-'0'; if(f) return -a; return a; } void init(){ for(int i=1;i<=n;i++){ c[i]=a[i]; for(int j=1;j<lb(i);j<<=1) c[i]=max(c[i],c[i-j]); } } void update(int x,int s){ //将点x改为 改为 改为s a[x]=s; for(;x<=n;x+=lb(x)){ c[x]=s; for(int i=1;i<lb(x);i<<=1) c[x]=max(c[x],c[x-i]); } } int ask(int l,int r){ int ans=a[r]; while(1){ ans=max(ans,a[r]); if(l==r) break; for(r--;r-lb(r)>=l;r-=lb(r)) ans=max(ans,c[r]); } return ans; }public: void work(){ int m; while(~scanf("%d%d",&n,&m)){ memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) a[i]=gnum(); init(); for(int i=1;i<=m;i++){ int opt=gnum(),u=gnum(),v=gnum(); if(opt==-21) update(u,v); if(opt==-17) printf("%d/n",ask(u,v)); } } }};int main(){ Binary_Tree4 tree; tree.work();}O(∩_∩)O收工~
新闻热点
疑难解答
