首页 > 代码库 > PAT-1057. Stack (30)--树状数组
PAT-1057. Stack (30)--树状数组
今天新学了一个知识，叫做线状数组，主要应用领域
1，数据频繁更新
2，求解某一段区间的和
以上产景情况下可以使用线状数组，更新某一个数据和求某一段时间之和时间复杂度都是Log(N) {常规情况是O(1)和O(N)}
线状数组和RMQ差不多，都可以再Log(N)时间复杂度内求解某一段区间的长度，线状数组额实现方式更为简单，更为方便
以下可以当做线段树的模板
主要函数有lowbit给定制定数字二进制下在末尾为0的个数。
Update更新某一节点的值。
getsum求解某一区间的值
Update是从叶子到根顶部跟新，getsum是从上至下更新，父子节点的差距就是lowbit(n)；
求解一段区间的和为什么可以用来求解中位数呢？
声明数组，初始化为0，当某个数出现的时候，比如10,那么tree[10]=1; 比如查找1-100就可以知道100以内有多少个数据存在了。
有一个问题比如
1 2 3 4 5 6 7 8 9 10
0 0 0 1 0 0 1 0 1 0
那么求解1-4的和为1
求解1-5也为1，求解1-6也为1.那么我怎么知道是哪一个作为？
（编码的时候只有当l==r时候才返回值，也就是区间左右都相等的时候才返回值，否则不返回值，如果是getsum(mid)==mid不做特殊处理。最初写成返回return mid
还是树状数组理解不够深。。待续。。。
）
// 1057.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include<string>#include<stack>using namespace std;#define MAX 100010stack<int> s;int tree[MAX]={0};int lowbit(int ind){ return ind & -ind;}void update(int ind,int val){ while(ind<=MAX) { tree[ind]+=val; ind+=lowbit(ind); }}int getsum(int ind){ int sum=0; while(ind>0) //not >=0 { sum+=tree[ind]; ind-=lowbit(ind); } return sum;}int findmid(int number,int l,int r){ if(l==r) return l; int mid=(l+r)/2; int sum=getsum(mid); if(sum<number) { return findmid(number,mid+1,r); } else { return findmid(number,l,mid); } /* 最后return mid会出错 */}int main(){ int num; string op; char op_name[15]; int tmp; freopen("1057.txt","r",stdin); while(scanf("%d",&num)!=EOF) { for(int i=0;i<num;i++) { scanf("%s",op_name); op=string(op_name); if(op=="Pop") { if(!s.empty()) { tmp=s.top(); update(tmp,-1); printf("%d\n",tmp); s.pop(); } else { printf("Invalid\n"); } } if(op=="Push") { scanf("%d",&tmp); s.push(tmp); update(tmp,1); } if(op=="PeekMedian") { int size=s.size(); if(size==0) { printf("Invalid\n"); continue; } if(size%2==0) size=size/2; else size=(size+1)/2; int mid=findmid(size,1,MAX); printf("%d\n",mid); } } } return 0;}
PAT-1057. Stack (30)--树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。