分块算法

----------------------------------------------------------

1.思想

如果我们需要对一个特定的序列进行操作，那么非常直观、简单的方法就是纯暴力（不，那叫模拟）。

不过如果暴力能过的话，那就呵呵了。

所以我们要想一些比较高能的数据结构——分块。

相比线段树来说，分块算法比较难实现，但是只要深入理解，就可以实现了，只不过需要一些数据结构的辅助。

分块实质来说就是把一个序列切分，从而实现对查询、查找、替换等等操作的高效处理。

----------------------------------------------------------

2.辅助结构

我们知道，数组的单点查询时间为O(1),而插入为O(n)

链表的单点查询时间为O(n),而插入为O(1)

而在NOIP里，vector总体来说是比数组快的，所以我们可以用vector来储存每块，只不过如果让插入也这用vector的话，那么时间就不可理喻了。

插入的话，我们可以使用pair

通常要定义这两个数据结构，简单的话那个pair就不用了，这要根据题意定义。

----------------------------------------------------------

3.模版

操作：建块（rebuild）

注意：一开始不必要建块，但是要在过程中将序列分块

用途：当当前块太大时，可以使用此函数将一个大块分裂

                            
void
rebuild()
{ 
    
top=0;
    
for
(
int
i=1;i<=m;i++)
    
{ 
        
for
(vector<
int
>::iterator j=ve[i].begin();j!=ve[i].end();j++)
            
st[++top]=*j;
        
ve[i].clear();
//清空当前块
    
}
    
int
blo2=sqrt(top);
    
for
(
int
i=1;i<=top;i++)
        
ve[(i-1)/blo2+1].push_back(st[i]);
    
m=(top-1)/blo2+1;
}
         
       

操作：区间加法（add）

注意：blo是分块一个重要的变量，是N的开方，大家可以仔细想一想为什么

用途：在需要操作区间加法时可以使用

                            
void
add(
int
a,
int
b,
int
c)
{ 
    
for
(
int
i=a;i<=min(bl[a]*blo,b);i++)
        
v[i]+=c,sum[bl[a]]+=c;;
    
if
(bl[a]!=bl[b])
        
for
(
int
i=(bl[b]-1)*blo+1;i<=b;i++)
            
v[i]+=c,sum[bl[b]]+=c;
    
for
(
int
i=bl[a]+1;i<=bl[b]-1;i++)
        
atag[i]+=c;
}
         
       

操作：插入

注意：自己可以控制块的大小

用途：插入元素

                            
void
insert(
int
a,
int
b)
{ 
    
pair<
int
,
int
> t=query(a);
    
ve[t.first].insert(ve[t.first].begin()+t.second,b);
    
if
(ve[t.first].size()>20*blo)
//分裂大块
        
rebuild();
}
         
       

常用的分块只有这几个操作，更多操作可见hzwer

转载于:https://www.cnblogs.com/Renyi-Fan/p/8116926.html

你可能感兴趣的文章