现在这篇还不是很成熟、以后会慢慢改的，但是基本可看，因为代码有超详细的注释！
如果有错误恳求大佬指教。

基本概念：

设一个长度为N的序列，块的大小为S，从序列的第一个元素起，每S个元素被分为一块，若最终剩余的元素不足S个，令他们组成一块。一般来说存在两种操作，区间求和、区间加法。

当然在很多问题中使用传统数据结构会更加优秀，但是当所需要的信息无法快速合并，就只能使用分块。比如询问一个区间的众数。

加速原理：把数组分成若干个块，通过预处理的方式获得块的某些信息，在对块进行操作的时候直接查询即可无需遍历

但是要注意的是：树状数组>线段树>块状数组(分块)

树状数组：代码简单、常数小(有些时候真的会卡常)
线段树：代码复杂、功能强大、常数大
块状数组：代码复杂、常数大、能维护一些很难快速合并的数据

1.区间求和：

假设询问的区间是 [l,r] ，l所在的块为 bl ,r所在的块为 br

a.当给定区间在同一个块内，即bl=br时

​ 直接枚举 [l,r] 的答案时间 O(S)

b.当给定区间不在同一个块里，即bl<br

​ 那么区间就可以被分为三个部分

​ (1)[l,块bl的右端点]

​ (2)块[bl+1~br-1] 显然，当bl和br相邻时，这个部分将不存在

​ (3)[块br的右端点,r]

​ 对于(1)(3)还是直接枚举计算,对于(2)每个块的 预处理 块内元素和sum，枚举计算。时间复杂度 O(N/S)

2.区间加法：

a.给定区间在同一个块内

​ 直接枚举修改每个元素值，同时更新块bl的sum，时间 复杂度O(S)

b.给定区间不在同一个块内

​ 同上，区间被分为3个部分，且在同一个区间内(1)(3)直接枚举修改

​ 对于(2)每个块不采取遍历的方式，而是维护两个值add(块内每个元素共同累加的数字)和sum。时间复杂度 O(N/S+S) ,显然当S=sqrt(N)时时间复杂度为最小 O(sqrt(N))

例题与代码实现：

基本概念中所阐述的逻辑是较为简单的，但是依旧是 太菜 无法用代码来实现。在学习很多算法的时候都是这样的，其背后的原因就是没有讲具体实现方法，即预处理如何处理。

例题：给定序列an,编号1~n,求a{j}-a{i}的最大值(1<=i<=j<=n)

/*
    Name:最优贸易简化版(分块算法) 
    Author:wyz
    Date:2019/4/6 10:22:46
    Note:
    题目大意：给定序列an,编号1~n,求a{j}-a{i}的最大值(1<=i<=j<=n) 

*/

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 1e6+5,INF=0x3f3f3f3f;
int a[MAXN],MI[320],MA[320],V[320];//a储存序列,MI储存块内最小值,MA储存块内最大值
int s;//定义块的大小
int query(int l,int r){
    int bl=l/s,br=r/s,res=0;//块左,块右,最大利润
    int mi=a[l];//初始化最小值 
    if(bl==br){//如果在同一个区间内直接暴力
        //res等于res和a[i]-前缀最小值的最大值 
        for(int i=l+1;i<=r;i++){
            res = max(res,a[i]-mi);
            mi = min(mi,a[i]);
        } 
    }   else    {
        //将区间分成三个区间 
        //左边不完整区间
        for(int i=l+1;i<(bl+1)*s;i++){//小于下一块的起始位置 
            res = max(res,a[i]-mi);
            mi = min(mi,a[i]);
        }//显然，经过循环此时的mi为 bl块内 && 区间内 最小值    
        //中间完成区间
        for(int i=bl+1;i<br;i++){//此处i表示块编号
            //这里同样是前缀最小值的思想,这里的前缀是在块编号之上 
            //最大利润 = 前一块的最大利润 和 当前块内交易 和 块内元素最大值-前i块内所有元素的最小值 的最大值 
            res = max(max(V[i],MA[i]-mi),res); 
            mi = min(mi,MI[i]);//更新前i块元素最小值 
        }
        //右边不完整区间 
        for(int i=br*s;i<=r;i++){//从当前块的起始坐标开始 
            res = max(res,a[i]-mi);
            mi = min(mi,a[i]);
        }
        //由此可见首区间和尾区间必然为不完整区间,即必然暴力求解 
    }
    return res;
}
int main(){
//  freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
    int n,m,si;
    cin>>n>>m;//数据量小可以直接用cin
    for(int i=1;i<=n;i++)scanf("%d",a+i);//数据量大用scanf,cin在不提速的情况下可以使用scanf
    /*
        cin/cout效率低的原因是:
        cin/cout会先把要输入/输出的东西放入缓冲区，再输出。
        ios::sync_with_stdio(false);
        可以来取消iostream的输入、输出缓存，使其效率接进scanf和printf的输入输出效率。
    */
    //预处理
    s=sqrt(n);//设定块的大小,query内的复杂度为O(s/n+s)所以s=srqt(n)复杂度最小 
    for(int i=0;i<=n/s;i++){
        MI[i]=INF;//每块的最小值为INF
        MA[i]=0;//每块的最大值为0
        V[i]=0;//每个块内交易的最大利润为0 
    }
    for(int i=1;i<=n;i++){
        si=i/s;//第i个元素的块编号为i
        /*
          重点：已经经历过初始化,思路类似与前缀和 
          V[si],i 表示的的是前i个元素的最大利润
          MI[i] 表示前i个元素的最小值
          MA[i] 表示前i个元素的最大值 
          走到i时当前块的最大利润应该是：
        */ 
        //走到当前块的最大利润和i的值-当前块之前所有元素的最小值      
        V[si]=max(V[si],a[i]-MI[si]);
        //更新当前块的最大最小值 
        MA[si]=max(MA[si],a[i]); 
        MI[si]=min(MI[si],a[i]); 
    }
    int l,r;
    while(m--){
        cin>>l>>r;
//      cout<<"查询结果"<<l<<" "<<r<<" ";
        cout<<query(l,r)<<endl;
    }
    return 0;
}