划分树

算是线段树的一种变形
线段树维护每个element的绝对位置不变。
划分树维护每个element保持相对位置。

教程 网上去搜
https://njzwj.github.io/2017/06/29/partition-tree-notes-1/
话说 挺喜欢这种自建blog，对于什么网易 新浪 等等。。广告太影响阅读

流程

• 线段树结构SegTree，初始化时候直接下放到底。

  • 其中lccnt 表示到i位置（包括rank[i]），有多少数被下放到了left-child。
  • rank 就是走到当前节点了，有哪些离散化过的值。。
• 然后读原数据，读完做离散化MakeInitRank()，然后把rank填到root->rank。
• 初始化线段树function buildTree()直接下放到底。
• 对于每次查询，执行query()，原理是不断的缩小query-left，query-right间距，如果碰上了就是答案。

Template

struct SegTree {
    int ll,rr;//The same affact with normal segment tree.
    vector<int> lccnt, rank;//special for 
    SegTree *lc, *rc;
    SegTree (int l, int r) {
        ll=l, rr=r;
        lc=rc=nullptr;
        rank = vector<int>(rr-ll+1);
    };
    int size() { return rr-ll+1; };
}*root=nullptr;

int discrete[MAXN];
void makeInitRank(vector<int> &rnk) {//discretize
    for (int i=0; i<n; i++)
        discrete[i]=i;
    auto cmp=[](const int &lhs, const int &rhs) { return data[lhs]<data[rhs]; };
    sort(discrete, discrete+n, cmp);
    for (int i=0; i<n; i++)// also ignore duplicate.
        rnk[ discrete[i] ]=i;
}
void buildTree(SegTree *t) {
    if (t->ll == t->rr)// The leaf Node don't have t->lccnt[].
        return ;
    int mid=( (t->ll+t->rr)>>1 );
    t->lc = new SegTree(t->ll, mid);
    t->rc = new SegTree(mid+1, t->rr);
    t->lccnt = vector<int>(t->size());
    for (int i=0, lsave=0, rsave=0, cnt=0; i<t->size(); i++) {
        if (t->rank[i] <= mid)
            t->lc->rank[lsave++]=t->rank[i], cnt++;
        else
            t->rc->rank[rsave++]=t->rank[i];
        t->lccnt[i]=cnt;
    }
    buildTree(t->lc);
    buildTree(t->rc);
}

//query lb:left-boundry, rb:right-boundry.
int query(SegTree *t, int lb, int rb, int kth) {
    if (t->ll==t->rr)
        return t->rank[0];
    int totalInLeft = t->lccnt[rb] - (lb>0?t->lccnt[lb-1]:0);
    if (kth <= totalInLeft) {// k-th fallen in left-child.
        int nxtL = (lb>0?t->lccnt[lb-1]:0);
        return query(t->lc, nxtL, t->lccnt[rb]-1, kth);
    }else {// k-th element fallen into right-child.
        int nxtL = (lb>0?lb-t->lccnt[lb-1]:0);
        int nxtR = rb - t->lccnt[rb];
        return query(t->rc, nxtL, nxtR, kth-totalInLeft);
    }
}
int main() {
    int n,data[MAXN];//original data.
    cin>>n>>m;
    for (int i=0; i<n; i++)
        cin>>data[i];
    root = new SegTree(0,n-1);
    makeInitRank(root->rank);
    buildTree(root);
    //query
    for (int i=0; i<m; i++) {
        int a,b,kth;//query : In [a,b] k-th element. (include [a] & [b])
        cin>>a>>b>>kth;
        a--,b--;//a&b in read stream is starting at 1.
        int fd=query(root, a, b, kth);
        cout<<data[discrete[fd]]<<endl;
    }
    /*
    A sample test data:
    data[] = 9 8 6 5 4
    Query 2 4 2  ==>>  6
    Query 1 1 1  ==>>  9
    Query 1 5 2  ==>>  5
    */
    return 0;
}

几个优化

频繁申请内存耗时间，咋办，可以弄一个pool，然后把上述每个vector换成一个指针，指向在pool里的起点。。。
另外还有一个叫主席树的。。似乎也能做？？。。。