Tag Archives: RMQ

LeetCode Range Sum Query – Mutable

LeetCode Range Sum Query – Mutable Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. The update(i, val) function modifies nums by updating the element at index i to val. Example:

Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

给定一个一维数组,要求实现范围求和,即求[i,j]之间的元素的和。sumRange(i,j)求i~j的元素和,update(i,val)更新下标为i的元素值为val。 第一敏感使用线段树,很久之前在hihoCoder上遇到过。 建树的方法是类似于树的后序遍历,即左右根。不断把[start,end]二分,构建左右子树,然后构建当前节点,当前节点的sum等于左右子树的sum的和。在递归的时候,递归到start==end时,说明只有一个元素了,此时sum就等于该元素。 查询的方法和建树方法类似,判断区间[i,j]和区间[start,end]的关系,假设start和end的中点是mid,如果j<=mid,递归在左子树查询;如果i>mid,递归在右子树查询;否则在[i,mid]和[mid+1,j]查询然后求和。 更新的方法和查询的方法类似,也是不断判断i和mid的关系,在左子树或者右子树递归更新,当找到该叶子节点时,更新它的sum,返回父节点也更新sum等于新的左右子树的sum的和。 完整代码如下: [cpp] class NumArray { private: struct Node { int start, end, sum; Node *left, *right; Node(int s, int e) :start(s), end(e), sum(0), left(NULL), right(NULL) {}; }; Node *root; Node* constructTree(vector<int> &nums, int start, int end) { Node* node = new Node(start, end); if (start == end) { node->sum = nums[start]; return node; } int mid = start + (end – start) / 2; node->left = constructTree(nums, start, mid); node->right = constructTree(nums, mid + 1, end); node->sum = node->left->sum + node->right->sum; return node; } int sumRange(int i, int j, Node *root) { if (root == NULL)return 0; if (i == root->start&&j == root->end)return root->sum; int mid = root->start + (root->end – root->start) / 2; if (j <= mid)return sumRange(i, j, root->left); else if (i > mid)return sumRange(i, j, root->right); else return sumRange(i, mid, root->left) + sumRange(mid + 1, j, root->right); } void update(int i, int val, Node *root) { if (root->start == root->end && root->start == i) { root->sum = val; return; } int mid = root->start + (root->end – root->start) / 2; if (i <= mid)update(i, val, root->left); else update(i, val, root->right); root->sum = root->left->sum + root->right->sum; } public: NumArray(vector<int> nums) { root = NULL; if (!nums.empty())root = constructTree(nums, 0, nums.size() – 1); } void update(int i, int val) { if (root == NULL)return; update(i, val, root); } int sumRange(int i, int j) { if (root == NULL)return 0; return sumRange(i, j, root); } }; [/cpp] 本代码提交AC,用时172MS。]]>

hihoCoder 1077-RMQ问题再临-线段树

hihoCoder 1077-RMQ问题再临-线段树 #1077 : RMQ问题再临-线段树 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到:小Hi给小Ho出了这样一道问题:假设整个货架上从左到右摆放了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量。但是在这个过程中,可能会因为其他人的各种行为,对某些位置上的商品的重量产生改变(如更换了其他种类的商品)。 小Ho提出了两种非常简单的方法,但是都不能完美的解决。那么这一次,面对更大的数据规模,小Ho将如何是好呢? 提示:其实只是比ST少计算了一些区间而已 输入 每个测试点(输入文件)有且仅有一组测试数据。 每组测试数据的第1行为一个整数N,意义如前文所述。 每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。 每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数与商品的重量被更改的次数之和。 每组测试数据的第N+4~N+Q+3行,每行分别描述一次操作,每行的开头均为一个属于0或1的数字,分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行,如果该行描述一个询问,则接下来为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri];如果该行描述一次商品的重量的更改,则接下来为两个整数Pi,Wi,表示位置编号为Pi的商品的重量变更为Wi 对于100%的数据,满足N<=10^6,Q<=10^6, 1<=Li<=Ri<=N,1<=Pi<=N, 0<weight_i, Wi<=10^4。 输出 对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。 样例输入 10 3655 5246 8991 5933 7474 7603 6098 6654 2414 884 6 0 4 9 0 2 10 1 4 7009 0 5 6 1 3 7949 1 3 1227 样例输出 2414 884 7474


这一题是hihoCoder Problem 1070:RMQ问题再临的升级版,数据量提升到10^6,但提示还是用线段树来解决。我原本以为只要把之前的数组大小改为10^6就行了,没想到这次居然给我报CE错。 第一次遇到这种错误,看了半天没明白什么意思,后来多方查找才得知可能是数组太大了,直接编译就不通过,想想看10^6的二维数组:10^6*10^6=10^12,装的是int,则总大小为4*10^12B=3725G,这明显大大超出了内存范围,而之前的10^4二维数组只有4*10^8B=381M,按理说也超出了题目的256MB,不过还是险些AC了,但是这一次就没这么好运了,所以必须优化算法! 怎样优化内存空间呢?先把我们的线段树请出来看看: 上图是线段树的一个例子,每个节点保存了区间范围以及该区间的最小值。总的区间大小是[1,10],仔细看看这个区间树的节点个数只有19个;另外再画一个[1,6]区间上的区间树,节点个数只有11个。可以不加证明的得出一个n的区间长度的线段树的节点个数为2*n-1,这远远小于n*n,所以我们只需要O(n)的空间来存储,而不是O(n^2)。 反观之前hihoCoder Problem 1070:RMQ问题再临的解法,其实没有构造一个真正的线段树,所以浪费了很多空间,那么怎样来构造一个真正的线段树呢? 我们知道常规的树形结构是用链表来实现的,每一个节点都有指向其左右孩子节点的指针,这样就可以很容易的访问孩子节点,如果用数组的结构来表示链表的结果,是不是会简单很多呢?于是我们定义如下树的节点结构: [cpp] typedef struct node//线段树节点 { int l;//区间左端点 int r;//区间右端点 int minv;//区间最小值 }; [/cpp] 再定义一个表示树的数组node tree[2*MAX_N];很自然的tree[i]的左右孩子节点分别存储在tree[2i]和tree[2i+1],这样是不是也很容易访问孩子节点了呢。 不论是创建、查询、更新树,都是从树根开始递归往下,这个过程和之前的那个题目类似,这里就不再赘述了。完整的代码如下: [cpp] #include<iostream> #include<cstdio> using namespace std; const int MAX_N=1e6+2; int w[MAX_N]; int n,q; typedef struct node//线段树节点 { int l;//区间左端点 int r;//区间右端点 int minv;//区间最小值 }; node tree[2*MAX_N]; inline int get_min(int a,int b) { return a<b?a:b; } //创建树 void build(int l,int r,int pos) { tree[pos].l=l; tree[pos].r=r; if(l==r) tree[pos].minv=w[l]; else { int mid=(l+r)/2; build(l,mid,pos*2); build(mid+1,r,pos*2+1); tree[pos].minv=get_min(tree[pos*2].minv,tree[pos*2+1].minv); } } //查询树 int query(int l,int r,int pos) { if(l==tree[pos].l&&r==tree[pos].r) return tree[pos].minv; int mid=(tree[pos].l+tree[pos].r)/2; if(r<=mid) return query(l,r,pos*2); else if(l>mid) return query(l,r,pos*2+1); else { int left=query(l,mid,pos*2); int right=query(mid+1,r,pos*2+1); return get_min(left,right); } } //更新树 void update(int pi,int wi,int pos) { if(tree[pos].l==tree[pos].r&&tree[pos].l==pi) tree[pos].minv=wi; else { int mid=(tree[pos].l+tree[pos].r)/2; if(pi<=mid) update(pi,wi,pos*2); else update(pi,wi,pos*2+1); tree[pos].minv=get_min(tree[pos*2].minv,tree[pos*2+1].minv); } } int main() { //freopen("input.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&w[i]); build(1,n,1); scanf("%d",&q); int p,l,r; for(int i=0;i<q;i++) { scanf("%d%d%d",&p,&l,&r); if(p==0) printf("%d\n",query(l,r,1)); else update(l,r,1); } return 0; } [/cpp] 本代码提交AC,用时697MS,内存45MB。 P.S.之前用cin、cout超时,改成scanf、printf就好了,懒得取消同步什么的,以后就打算一直用scanf、printf了。唉,从上一题到这一题,优化是无止境的啊~~]]>

hihoCoder 1070-RMQ问题再临

hihoCoder 1070-RMQ问题再临 #1070 : RMQ问题再临 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 终于,小Hi和小Ho踏上了回国的旅程。在飞机上,望着采购来的特产——小Hi陷入了沉思:还记得在上上周他们去超市的时候,前前后后挑了那么多的东西,都幸运的没有任何其他人(售货员/其他顾客)来打搅他们的采购过程。但是如果发生了这样的事情,他们的采购又会变得如何呢? 于是小Hi便向小Ho提出了这个问题:假设整个货架上从左到右摆放了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量。但是在这个过程中,可能会因为其他人的各种行为,对某些位置上的商品的重量产生改变(如更换了其他种类的商品),面对这样一个问题,小Ho又该如何解决呢? 提示:平衡乃和谐之理 输入 每个测试点(输入文件)有且仅有一组测试数据。 每组测试数据的第1行为一个整数N,意义如前文所述。 每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。 每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数与商品的重量被更改的次数之和。 每组测试数据的第N+4~N+Q+3行,每行分别描述一次操作,每行的开头均为一个属于0或1的数字,分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行,如果该行描述一个询问,则接下来为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri];如果该行描述一次商品的重量的更改,则接下来为两个整数Pi,Wi,表示位置编号为Pi的商品的重量变更为Wi 对于100%的数据,满足N<=10^4,Q<=10^4, 1<=Li<=Ri<=N,1<=Pi<=N, 0<weight_i, Wi<=10^4。 输出 对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。 样例输入 10 618 5122 1923 8934 2518 6024 5406 1020 8291 2647 6 0 3 6 1 2 2009 0 2 2 0 2 10 1 1 5284 0 2 5 样例输出 1923 2009 1020 1923


本题的数据量比hihoCoder Problem 1068: RMQ-ST 算法这题要小,虽然
用O(N)的时间进行计算——扫描一遍整个区间找到最小值,然后对于每一个更改操作,使用O(1)的时间直接进行修改,这样也就是O(NQ)的总时间复杂度!在这种数据量下完全是可以通过的!
但是本题希望我们用线段树来解决。 我曾在《数据结构》的改造红黑树中看到过区间树,但是本题的线段树和书中的区间树有所区别,区间树由红黑树改造而来,结构更复杂些,这里只需要使用线段树即可。 常规的线段树如下图所示: 从图中可以看到构造线段树的过程就是一个二分的过程,不断将区间分成两半,直到只有一个元素。图中的线段树每一个节点是一个区间[l,r],本题我稍微改造了一下,改成了数组int seg_tree[left][length],比如seg_tree[i][j]表示从下标i开始,长度为j的这样一个区间上的最小值,这样就可以利用线段树来解决RMQ问题了。比如改造后的线段树就成了下面的样子: 因为树形这种特殊的结构,我们可以用一个DFS来对树实现二分构造,当DFS到某个节点长度为1时,其最小值就是w[i]本身,在回溯到父节点时,父节那个区间的最小值又是所有子节点最小值中的最小值。因为树的总节点数大约为2*n,所以复杂度O(n)。 当需要查询区间[l,r]的最小值时,只需对数组seg_tree二分搜索。具体来说,假设我们搜索到了节点[s_l,s_len],如果r<(s_l+s_len/2),说明区间[l,r]全在[s_l,s_len]的左边,我们递归在[s_l,s_len/2]区间找;如果l>=(s_l+s_len/2),说明区间[l,r]全在[s_l,s_len]的右边,我们递归在[s_l+s_len/2,s_len-s_len/2]区间找;如果以上两者都不是,说明[l,r]跨界了,而且中点下标一定是s_l+s_len/2,所以我们分别在二两半区间找,然后求这两者的最小值。复杂度O(lgn)。 当需要更新某个下标为pos的值为value时,也是DFS查找线段树,直到找到叶子seg_tree[pos][1],更新它的值,以及所有我们在查找过程经过的父节点的值。复杂度O(lgn)。 所以线段是的性质使得无论是构造、查询、更新操作,复杂度都只要O(lgn),这就是题目中所说的把总的复杂度平均分配到不同操作:平衡乃和谐之理。 完整代码如下: [cpp] #include<iostream> using namespace std; const int MAX_N=1e4+2; int w[MAX_N];//每个商品重量 int n,m; int seg_tree[MAX_N][MAX_N];//seg_tree[i][j]:起点为i,长度为j的区间的最小值 inline int get_min(int a,int b) { return a<b?a:b; } //深度优先遍历以构造线段树 void dfs(int left,int length) { if(length==1) { seg_tree[left][1]=w[left]; return; } dfs(left,length/2); dfs(left+length/2,length-length/2); seg_tree[left][length]=get_min(seg_tree[left][length/2],seg_tree[left+length/2][length-length/2]);//取最小值 } //在区间[s_left,s_len]搜索区间[left,length]的最小值 int search_min(int s_left,int s_len,int left,int length) { if((s_left==left)&&(s_len==length)) return seg_tree[s_left][s_len]; if((left+length-1)<(s_left+s_len/2))//全在左半部分 { return search_min(s_left,s_len/2,left,length); } else if(left>=(s_left+s_len/2))//全在右半部分 { return search_min(s_left+s_len/2,s_len-s_len/2,left,length); } else//左右分开搜索 { int left_len=s_left+s_len/2-left; int right_len=length-left_len; int min_left=search_min(s_left,s_len/2,left,left_len); int min_right=search_min(s_left+s_len/2,s_len-s_len/2,s_left+s_len/2,right_len); return get_min(min_left,min_right); } } //从区间[s_left,s_len]开始更新下标pos的值为value void update(int s_left,int s_len,int pos,int value) { if((s_left==pos)&&(s_len==1)) { seg_tree[s_left][1]=value; return ; } int mid=s_left+s_len/2; if(pos<mid) update(s_left,s_len/2,pos,value); else update(mid,s_len-s_len/2,pos,value); seg_tree[s_left][s_len]=get_min(seg_tree[s_left][s_len/2],seg_tree[mid][s_len-s_len/2]);//更新父节点 } int main() { //freopen("input.txt","r",stdin); cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; dfs(1,n); cin>>m; int p,l,r; for(int i=0;i<m;i++) { cin>>p>>l>>r; if(p==0)//查询 { cout<<search_min(1,n,l,r-l+1)<<endl; } else//修改 { update(1,n,l,r); } } return 0; } [/cpp] 本代码提交AC,用时151MS,内存42MB。 ]]>

hihoCoder 1069-最近公共祖先·三

hihoCoder 1069-最近公共祖先·三 #1069 : 最近公共祖先·三 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上上回说到,小Hi和小Ho使用了Tarjan算法来优化了他们的“最近公共祖先”网站,但是很快这样一个离线算法就出现了问题:如果只有一个人提出了询问,那么小Hi和小Ho很难决定到底是针对这个询问就直接进行计算还是等待一定数量的询问一起计算。毕竟无论是一个询问还是很多个询问,使用离线算法都是只需要做一次深度优先搜索就可以了的。 那么问题就来了,如果每次计算都只针对一个询问进行的话,那么这样的算法事实上还不如使用最开始的朴素算法呢!但是如果每次要等上很多人一起的话,因为说不准什么时候才能够凑够人——所以事实上有可能要等上很久很久才能够进行一次计算,实际上也是很慢的! “那到底要怎么办呢?在等到10分钟,或者凑够一定数量的人两个条件满足一个时就进行运算?”小Ho想出了一个折衷的办法。 “哪有这么麻烦!别忘了和离线算法相对应的可是有一个叫做在线算法的东西呢!”小Hi笑道。 小Ho面临的问题还是和之前一样:假设现在小Ho现在知道了N对父子关系——父亲和儿子的名字,并且这N对父子关系中涉及的所有人都拥有一个共同的祖先(这个祖先出现在这N对父子关系中),他需要对于小Hi的若干次提问——每次提问为两个人的名字(这两个人的名字在之前的父子关系中出现过),告诉小Hi这两个人的所有共同祖先中辈分最低的一个是谁? 提示:最近公共祖先无非就是两点连通路径上高度最小的点嘛! 输入 每个测试点(输入文件)有且仅有一组测试数据。 每组测试数据的第1行为一个整数N,意义如前文所述。 每组测试数据的第2~N+1行,每行分别描述一对父子关系,其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i,分别表示父亲的名字和儿子的名字。 每组测试数据的第N+2行为一个整数M,表示小Hi总共询问的次数。 每组测试数据的第N+3~N+M+2行,每行分别描述一个询问,其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i,分别表示小Hi询问中的两个名字。 对于100%的数据,满足N<=10^5,M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),所有询问中出现过的名字均在之前所描述的N对父子关系中出现过,且每个输入文件中第一个出现的名字所确定的人是其他所有人的公共祖先。 输出 对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:他们的所有共同祖先中辈分最低的一个人的名字。 样例输入 4 Adam Sam Sam Joey Sam Micheal Adam Kevin 3 Sam Sam Adam Sam Micheal Kevin 样例输出 Sam Adam Adam


这应该是最近公共祖先的最后一种算法了吧,hihoCoder还真是循序渐进啊,昨天刚刚学了RMQ-ST算法hihoCoder Problem 1068: RMQ-ST 算法,今天就用上了。 本题的解题思路也是非常的赞,首先把族谱树结构展开成一个数组B,当询问a,b节点的最近公共祖先时,在B中找到a,b最后出现的位置(也就是离开a,b节点的时候)an,bn,在区间[an,bn]上利用RMQ-ST算法求解区间深度最小的节点c,则c即为a,b的最近公共祖先,下面来具体讲解。 将族谱树展开成一个数组 为了利用RMQ-ST算法,需要将树形结构展开成一个数组,展开的方式是深度优先遍历树,将访问的节点顺序记录下来,不管是进入这个节点还是离开这个节点,都需要记录下来。比如下面一棵树: 是样例输入构成的一个家谱树,我们常规DFS这个树的序列是这样的:ASJMK。但是本题在进入和离开某个节点时都需要记录下来,而且每访问完一个子节点,要访问下一个子节点时,也需要记录当前父节点。比如访问完J准备访问M时,需要记录S,由此形成的序列为:ASJSMSAKA。 DFS生成的数组B长度大概为边数的两倍,所以复杂度级别只是O(n)的。 DFS之后就把树转换为了数组B[],因为使用RMQ-ST算法需要求某个区间的最小深度节点,所以在DFS的时候还需要记录每个节点的深度信息,而且还要记录每个节点最后访问的下标,这两点都不难,大家直接看代码即可。 RMQ-ST算法 得到数组B后就好办了,可以利用昨天学习的RMQ-ST算法求解2的幂区间长度间深度最小的节点,不过因为我们这题最终输出的是节点的名字而不是节点的深度,所以RMQ-ST比较的是深度,但存储的是节点名。 观察RMQ-ST算法的二重循环知道其复杂度为O(nlgn)。 在线求解 一切准备就绪后就可以求解了,首先根据字符串名字找到对应数字序号,然后查看两节点最后出现在树中的下标l,r,再讲[l,r]区间分成能覆盖[l,r]的2的幂的长度的半区间[l,t]和[t+1,r],最后求这两个区间最小深度的节点,输出其名称。 完整代码如下: [cpp] #include<iostream> #include<map> #include<string> #include<vector> #include<cmath> using namespace std; const int MAX_N=100010;//最大人数 map<string,int> name_index;//名字转换为数字 vector<string> index_name(MAX_N);//数字转换为名字 int n,m,k;//k全部记录将树转换成数组tree[]是的下标,转换结束时k即为tree[]的长度 vector<vector<int> > f_s(MAX_N);//f_s[i]表示第i个父亲的所有孩子 int tree[2*MAX_N];//DFS将树转换为的数组 int depth[MAX_N];//每个点在树中的深度 int rmq[MAX_N][30];//区间深度最低值 int last_show[MAX_N];//某个元素最后出现在tree中的位置(下标) //保存某个人的信息,并返回其下标 int store_name(string name) { map<string,int>::iterator it=name_index.find(name); if(it==name_index.end())//还不存在 { int curr_index=name_index.size();//用当前已有人数作为其下标,正好是递增的。 name_index.insert(make_pair(name,curr_index)); index_name[curr_index]=name;//记录 return curr_index;//返回下标 } else return it->second;//已经存在,直接返回 } //深度遍历树 void DFS(int root,int deep) { tree[k++]=root;//进入即记录 depth[root]=deep;//记录深度 int sons=f_s[root].size(); for(int i=0;i<sons;i++) { DFS(f_s[root][i],deep+1); tree[k++]=root;//每返回一次都要记录一次根节点 } last_show[root]=k-1;//root节点最后出现的位置 } //求a,b最小值 inline int get_min(int a,int b) { return a<b?a:b; } void init_rmq() { for(int j=0;j<k;j++) //rmq[j][0]=depth[tree[j]]; rmq[j][0]=tree[j];//保存的是这个节点,而不是它的深度,方便最后输出 int q=floor(log((double)k)/log(2.0)); for(int i=1;i<=q;i++) { for(int j=k-1;j>=0;j–) { rmq[j][i]=rmq[j][i-1]; if(j+(1<<(i-1))<k) { if(depth[rmq[j+(1<<(i-1))][i-1]]<depth[rmq[j][i]])//+优先级高于<<,所以改j+1<<(i-1)为j+(1<<(i-1)) rmq[j][i]=rmq[j+(1<<(i-1))][i-1]; } //rmq[j][i]=get_min(rmq[j][i],rmq[j+1<<(i-1)][i-1]); } } } int main() { //freopen("input.txt","r",stdin); cin>>n; string name1,name2; int index1,index2; while(n–) { cin>>name1>>name2; index1=store_name(name1); index2=store_name(name2); f_s[index1].push_back(index2); } k=0;//开始时树的下标为0,DFS完之后正好是tree[]数组的长度,可以作为rmq-st的n DFS(0,0); init_rmq(); cin>>m; int l,r,t; while(m–) { cin>>name1>>name2; if(name1==name2) { cout<<name1<<endl; continue; } index1=store_name(name1); index2=store_name(name2); l=last_show[index1]; r=last_show[index2]; if(l>r)//保证l<=r { int tmp=r; r=l; l=tmp; } t=floor(log(double(r-l+1))/log(2.0));//找到能使[l,r]分为两半的指数 cout<<index_name[get_min(rmq[l][t],rmq[r-(1<<t)+1][t])]<<endl;//r-(1<<t)+1,记得+1 } return 0; } [/cpp] 本代码提交AC,用时202MS,内存8MB。 相比于hihoCoder Problem 1067: 最近公共祖先·二,本题的的DFS+RMQ-ST算法是在线算法,也就是每来一个询问可以立即回答,而且复杂度为O(nlgn)还不错。 至此,hihoCoder的最近公共祖先问题完整结束,共使用三种算法,后两种算法都利用DFS,阅读时可以互相参照:最近公共祖先问题]]>

hihoCoder 1068-RMQ-ST算法

hihoCoder 1068-RMQ-ST算法 #1068 : RMQ-ST算法 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 小Hi和小Ho在美国旅行了相当长的一段时间之后,终于准备要回国啦!而在回国之前,他们准备去超市采购一些当地特产——比如汉堡(大雾)之类的回国。 但等到了超市之后,小Hi和小Ho发现者超市拥有的商品种类实在太多了——他们实在看不过来了!于是小Hi决定向小Ho委派一个任务:假设整个货架上从左到右拜访了N种商品,并且依次标号为1到N,每次小Hi都给出一段区间[L, R],小Ho要做的是选出标号在这个区间内的所有商品重量最轻的一种,并且告诉小Hi这个商品的重量,于是他们就可以毫不费劲的买上一大堆东西了——多么可悲的选择困难症患者。 (虽然说每次给出的区间仍然要小Hi来进行决定——但是小Hi最终机智的选择了使用随机数生成这些区间!但是为什么小Hi不直接使用随机数生成购物清单呢?——问那么多做什么!) 提示一:二分法是宇宙至强之法!(真的么?) 提示二:线段树不也是二分法么? 输入 每个测试点(输入文件)有且仅有一组测试数据。 每组测试数据的第1行为一个整数N,意义如前文所述。 每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。 每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数。 每组测试数据的第N+4~N+Q+3行,每行分别描述一个询问,其中第N+i+3行为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri]。 对于100%的数据,满足N<=10^6,Q<=10^6, 1<=Li<=Ri<=N,0<weight_i<=10^4。 输出 对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。 样例输入 10 7334 1556 8286 1640 2699 4807 8068 981 4120 2179 5 3 4 2 8 2 4 6 8 7 10 样例输出 1640 981 1556 981 981


给出n个数字,连续q次问[l,r]区间的最小值是多少。如果每询问一次都用遍历的方式求最小值,则总的时间复杂度为O(nq)。 本题给出了一个新的算法–RMQ-ST算法,它的时间复杂度为O(nlogn+q),如果q很大,比如接近n时,RMQ-ST算法就有优势了。 RMQ-ST算法的基本思想是先计算某个小区间a的最小值,当需要计算大区间b的最小值时,把它分成两个小区间a1,a2,因为小区间的最小值之前已经计算出来了,也就是a1,a2已知,则b=min{a1,a2}。这样每次询问[l,r]区间的最小值时,我们也只需要把[l,r]分成两个[l,t]和[t+1,r]区间,取这两个区间最小值的最小值,这样的时间复杂度是O(1)。 所以关键就在于怎么求所有小区间的最小值。 根据提示,为了简便,我们只求2的幂的长度区间的最小值,设数组int pre_calc[i][j]为区间[i,i+2^j-1]的最小值(从i开始,长度为2^j的区间最小值),因为长度为1的区间的最小值就是其本身,所以有pre_calc[i][0]=weight[i]。 因为pre_calc[i][j]的长度为2^j,所以我们正好可以将其分成2个长度为2^(j-1)的区间,也就是说pre_calc[i][j]=min{pre_calc[i][j-1],pre[i+2^(j-1)][j-1]}。 这样我们就找到了pre_calc的递推公式(实质是DP里的状态转换方程),那么j的取值范围是怎样的呢?因为长度为n的数组其最大子区间长度就是n,所以j的最大值就是log(n),下面只需一个二重循环就可求解。 当来了一个询问[l,r]时,我们也需要将其分成两个长度为2的幂的子区间a和b,假设这个幂为t,为了使两个子区间完全覆盖[l,r],两个子区间甚至可以重叠,所以a的右边缘需要大于等于b的左边缘,即l+2^t>=r-2^t+1,得到t>=log(r-l+1)-1,所以我们可以取t=log(r-l+1)。 完整代码如下: [cpp] #include<stdio.h> #include<math.h> #define MAX_N 1000010 int n,q; int weight[MAX_N]; int pre_calc[MAX_N][30]; //求a,b最小值 int get_min(int a,int b) { return a<b?a:b; } //初始化 void init_pre() { for(int j=1;j<=n;j++) pre_calc[j][0]=weight[j]; int m=floor(log((double)n)/log(2.0));//指数最大值 for(int i=1;i<=m;i++) { for(int j=n;j>0;j–) { pre_calc[j][i]=pre_calc[j][i-1]; if(j+(1<<(i-1))<=n)//如果另一半也存在的话。//1<<(i-1)其实就是2^(i-1) pre_calc[j][i]=get_min(pre_calc[j][i],pre_calc[j+(1<<(i-1))][i-1]); } } } int main() { //freopen("input.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&weight[i]); init_pre(); scanf("%d",&q); int l,r,t; while(q–) { scanf("%d%d",&l,&r); t=floor(log(double(r-l+1))/log(2.0));//找到能使[l,r]分为两半的指数 printf("%d\n",get_min(pre_calc[l][t],pre_calc[r-(1<<t)+1][t])); } return 0; } [/cpp] 代码中求pre_calc时需要注意二重循环的顺序不要搞反了,因为我们是先求得小区间的最小值才能求大区间的最小值,所以第一重循环应该是区间的长度,而不是区间的起点。 本代码提交AC,用时875MS,内存138MB。(用cin,cout超时。。。) 这篇文章介绍了用RMQ-ST算法求解区间最大值和最小值的方法。]]>