分桶法和平方分割-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

分桶法和平方分割

阅读量：4322 次

发布时间：2019-06-06

本文共 1783 字，大约阅读时间需要 5 分钟。

分桶法：把一排物品或者平面分成桶，每个桶分别维护自己内部的信息，已到达高效计算的目的的方法。

其中，平方分割是把排成一排的n个元素每√n个分在一个桶内进行维护的方法的统称。这样的方法可以使对区间的操作复杂度降至O（√n）。

以RMQ为例：

基于平方分割的RMQ

给定一个数列a₁,a₂,a₃,a₄,a₅,a₆,....,a_n，目标是在O（√n）浮渣度内实现以下两个功能

给定s，t，求a_s,a_s+1,a_s+2,...,a_t的最小值。

给定i，x，把a_i的值变成x。

基于平方分割的RMQ预处理

令len=(int)(√n)，把a中的元素每len个分成一个桶，并且计算出每个桶内的最值。

基于平方分割的RMQ查询

如下图所示,查询

如果桶完全包含在区间内，则查询桶内的最小值。

如果元素所在的桶不完全被包含包含，则逐个检查最值。

它们的最值就是区间的最值了。

基于平方分割的RMQ的值的更新

在更新元素的值时，只需要更新该元素所在的桶的最值。

基于平方分割的RMQ的复杂度

在更新时，因为每个桶内有len个元素，所以复杂度是O（len）=√n

而在查询时

完全包含在区间内的桶的个数是O（n/len）

所在的桶不被区间完全包含的元素个数是O（len）

因为len=O（√n），所以操作复杂度是O（n/len+len）=O（√n+√n）=O（√n）

附上POJ 3246.的平方分割的RMQ写法

代码：

#include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;#define PI acos(-1.0)typedef long long ll;typedef pair
                
                  P;const int maxn=1e5+100,maxm=1e5+100,inf=0x3f3f3f3f,mod=1e9+7;const ll INF=1e13+7;priority_queue
                 
                  ,greater
                   >q;struct edge{ int from,to; int cost;};///分桶法+平方分割解决RMQ问题struct node{ int l,r; int mmin,mmax;} sign[maxn];int a[maxn];int main(){ int n,q; scanf("%d%d",&n,&q); int x=(int)(sqrt(n)); int t=0; for(int i=1; i<=n; i++) { scanf("%d",&a[i]); if(i%x==1) t++,sign[t].l=i,sign[t].r=i,sign[t].mmax=0,sign[t].mmin=inf; sign[t].mmin=min(sign[t].mmin,a[i]); sign[t].mmax=max(sign[t].mmax,a[i]); sign[t].r=i; } while(q--) { int l,r; scanf("%d%d",&l,&r); int mmax=0,mmin=inf; for(int i=1; i<=t; i++) { if(l>sign[i].r) continue; if(l>sign[i].l) { for(int j=l; j<=sign[i].r&&j<=r; j++) mmax=max(mmax,a[j]),mmin=min(mmin,a[j]); } else if(l<=sign[i].l&&sign[i].r<=r) mmax=max(mmax,sign[i].mmax),mmin=min(mmin,sign[i].mmin); else if(r

平方分割的RMQ

转载于:https://www.cnblogs.com/GeekZRF/p/7136623.html

你可能感兴趣的文章

Food HDU - 4292 (结点容量拆点) Dinic

Ubuntu安装Sun JDK及如何设置默认java JDK

[经典算法] 排列组合-N元素集合的M元素子集

Codeforces 279D The Minimum Number of Variables 状压dp

打分排序系统漫谈2 - 点赞量？点赞率?! 置信区间！

valgrind检测linux程序内存泄露

Hadoop以及组件介绍

1020 Tree Traversals (25)（25 point(s)）

第一次作业

“==”运算符与equals()

单工、半双工和全双工的定义

Hdu【线段树】基础题.cpp

5个基于HTML5的加载动画推荐

水平权限漏洞的修复方案

静态链接与动态链接的区别

Android 关于悬浮窗权限的问题

如何使用mysql

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-10-06 15:21:44 当前IP: 3.138.120.136 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我