学习笔记--分块基础

讲师：noip _Orz

• 相关介绍

  分块分静态和动态两种,动态分块才可以支持修改，下面我们都是讲动态分块。

  整块--操作完全覆盖的块

  零散块--操作不完全覆盖的块。

  分块保证每次操作最多经O(sqrt(n))个整块及O(1)个零散块

  • 分块作用：

    如果在分治结构上很难合并某些信息，就可以利用分块做。

• 基础模板

  block -> 块大小

  belong[i] -> i属于的块编号

  l[i] -> 第i块的左端点

  r[i] -> 第i块的右端点

  for( register int i = 1 ; i <= n ; i++ )
     belong[i] = ( i - 1 ) / block;
  for( register int i = 1 ; i <= n ; i++ )
    if( !l[ belong[i] ] )
        l[ belong[i] ] = i;
  for( register int i = n ; i ; i-- )
    if( !r[ belong[i] ] )
        r[ belong[i] ] = i;
  modify/find( int L , int R )
  if( belong[l] == belong[r] )
    for( register int i = L ; i <= R ; i++ )
        .......
  else
  {
    for( register int i = L ; i <= r[ belong[L] ] ; i++ )
        ......
    for( register int i = l[ belong[R] ] ; i <= R ; i++ )
        ......
    for( register int i = belong[L] + 1 ; i <=      belong[R] - 1 ; i++ )
        ......