BlockList（块状链表）

我们知道对于线性表，有两种基础的数据结构：数组和链表。

对于数组而言，支持O(1)的随机访问，结尾插入删除不考虑扩容可以近似认为是O(1)，而中间插入或删除则需要O(n)的时间移动插入点后的所有数据。

对于链表而言，不支持随机访问，访问第k个元素需要从头遍历需要O(n)的时间，而插入和删除只需要改变next指针即O(1)的时间，当然定位到插入删除点还是需要O(n)的时间。

如果我们把数组和链表结合起来，有链表连接大块的数组而不是单个元素，那么访问、插入、删除都会折中，有时这很有用，我们先思考这个大块数组要取多大合适，如果数据的最大长度是n，我们块大小取k，则会形成n/k个块，那么定位到任意一个元素的最坏时间是n/k(即在链表的最后一个结点上，需要从头遍历的时间)，而插入删除一个元素的最坏时间是k，即在大块的头上插入需要移动整个大块的数据。

k越大n/k越小，如果我们折中，显然是让k=n/k，即k=sqrt(n)。那么上述操作的复杂度最坏情况下都是O(sqrt(n))。

思路就是这么简单，还有一些实现细节，插入时考虑分裂大块，删除时考虑合并大块，具体直接看代码吧。

//一个节点的初始大小
const int NODESIZE=160; //如果数据大小最大为n，取在sqrt(n)/2会比较好，对于10w的数据这个大小应该比较优
//加上缓冲区一个节点应该占用NODESIZE*2的空间
//任何一个节点大小不会>=NODESIZE*2，任何两个相邻的节点大小不会<=NODESIZE

template<typename T>
class BlockList{
public:
    struct BLNode{
        T data[NODESIZE<<1];
        int size;//该结点中已经使用的大小
        BLNode* next;
        BLNode():size(0),next(NULL){}
    };
    BLNode* _head;
    BLNode* _tail;
    int _size; //整个表中的元素数

    void split(BLNode* p){
        BLNode* q = new BLNode();
        q->next = p->next;
        p->next = q;
        memcpy(q->data, p->data+NODESIZE, sizeof(T)*(p->size-NODESIZE));
        q->size = p->size-NODESIZE;
        p->size = NODESIZE;
        if(_tail == p) _tail = q;
    }

    void join(BLNode* p, BLNode* q) {
        memcpy(p->data+p->size, q->data, sizeof(T)*q->size );
        p->size += q->size;
        p->next = q->next;
        if(_tail == q) _tail = p;
        delete q;
    }
public:
    BlockList(int size=0, const T& val=T()):_size(size) {
        _head = _tail = new BLNode();
        if(size != 0) {
            while(size>NODESIZE){
                std::fill(_tail->data, _tail->data+NODESIZE, val);
                size -= NODESIZE;
                _tail->size = NODESIZE;
                if(!_tail->next) {
                    _tail->next = new BLNode();
                }
                _tail = _tail->next;
            }
            std::fill(_tail->data, _tail->data+size, val);
            _tail->size = size;
        }
    }
    int size(){return _size;}
    
    //通过下标随机访问，复杂度O(sqrt(size))
    T& operator [] (int i){
        assert(0<=i && i<_size);
        BLNode* p = _head;
        while(i>=p->size){
            i -= p->size;
            p = p->next;
        }
        return p->data[i];
    }

    //在尾部追加数据
    void push_back(const T& d) {
        _size++;
        _tail->data[_tail->size++] = d;
        if(_tail->size==(NODESIZE<<1)){
            split(_tail);
        }
    }
    
    //在下标i处插入数据d，原数据依次后移
    void insert(int i, const T& d){
        assert(0<=i && i<=_size);
        _size++;
        BLNode* p=_head;
        while(i>p->size){
            i -= p->size;
            p = p->next;
        }
        for(int j=p->size-1; j>=i; j--){
            p->data[j+1]=p->data[j];
        }
        p->data[i]=d;
        p->size++;
        if(p->size==(NODESIZE<<1)){
            split(p);
        }
    }

    //删除在下标i处的数据，后续数据依次前移
    void erase(int i){
        assert(0<=i && i<_size);
        _size--;
        BLNode* p=_head;
        while(i>=p->size){
            i -= p->size;
            p = p->next;
        }
        for(int j=i;j<p->size-1;j++){
            p->data[j]=p->data[j+1];
        }
        p->size--;
        BLNode* q = p->next;
        if(q && p->size+q->size<=NODESIZE){
            join(p, q);
        }
    }
};

406. 根据身高重建队列

这道题可以把人的身高从高到低排序，然后依次根据ki插入到数组的ki位置就可以了，如果用数组实现就是O(n^{2)的，改用块状链表可以降到O(n}1.5)

把初始结点大小取在16~32有可能跑出击败100%用户的时间，sqrt(2000)/2是22左右。

执行用时：
12 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：
11.6 MB, 在所有 C++ 提交中击败了82.61%的用户
通过测试用例：
36 / 36