「划分树」求区间第k大值

思路：将n个数的序列不断划分，根节点是原序列，左子树是原序列排序后较小的一半，右子树是另一半。留意，子数中的元素的相对位置是和父亲序列一样的，见图，这部分参考了这个博客：

其中，红色标记是进入左子树的元素。

首先，数组序号1开始数，树的层数从0开始数。
有2个辅助数组比较关键：
sorted[]: 是原始数列排序好的数组，用以决定哪些元素要放入左子树。
toLeft[d][i]，表示d层[1,i]下标中有多少个元素被置于左子树。以图的0层为例，看toLeft[0]，那么应该有:toLeft[0]={1，1，1，2，2，3，3，4}。

建树的时候，toLeft[dep][i]=toLeft[dep][l-1]+lpos-l。含义即dep层至i为止往左子树的元素数相当于早已前往左子树的toLeft[dep][l-1]数量，加上这次for循环新加入的往左的数量。

查询下标计算比较关键。[L,R]是大区间，[l,r]是查询的小区间，先查询[l,r]内有前往左子树的元素数量，记为cnt，若cnt>=k，意味着第k大数必然在左子树，否则去了右子树。

不论去哪，都要重新计算查询的区间。结合图分析计算

若往左。新的左起始下标应该是L+toLeft[dep][l-1]-toLeft[dep][L-1]，即seg1区间内往左走的元素，相当于越过seg1前往左子树元素后，才是[l,r]区间里往左走的元素起始点。新的右限自然是newl+cnt-1。

若往右。新的右起始点也应该去除[r, R]区间往左走的元素干扰，所以newr=r+toLeft[dep][R]-toleft[dep][r]，确定了右限，而[l,r]又往右去了(r-l+1-cnt)个元素(记为t)，那么左起始点就是newr-t+1了。别忘记[l,r]已经有cnt个往左子树走，往右则只需找k-cnt大元素即可。

模板题：poj 2104

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 1e5 + 5;
int N, M, T;

int tree[20][maxN];
int sorted[maxN];
int toLeft[20][maxN];

void build(int l, int r, int dep) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    int same = mid - l + 1;
    int smid = sorted[mid];
    rep(i, l, r + 1)
        if (tree[dep][i] < smid)
            --same;

    int lpos = l, rpos = mid + 1;
    rep(i, l, r + 1) {
        if (tree[dep][i] < smid) {
            tree[dep + 1][lpos++] = tree[dep][i];
        } else if (tree[dep][i] == smid && same > 0) {
            --same;
            tree[dep + 1][lpos++] = tree[dep][i];
        } else {
            tree[dep + 1][rpos++] = tree[dep][i];
        }
        toLeft[dep][i] = toLeft[dep][l - 1] + lpos - l;
    }
    build(l, mid, dep + 1);
    build(mid + 1, r, dep + 1);
}

// L R是大区间 l,r是查询区间,查询第k大值
int query(int L, int R, int l, int r, int dep, int k) {
    if (l == r) return tree[dep][l];
    int mid = (L + R) >> 1;
    int cnt = toLeft[dep][r] - toLeft[dep][l - 1];
    if (cnt >= k) {
        int newl = L + toLeft[dep][l - 1] - toLeft[dep][L - 1];
        int newr = newl + cnt - 1;
        return query(L, mid, newl, newr, dep + 1, k);
    } else {
        int newr = r + toLeft[dep][R] - toLeft[dep][r];
        int newl = newr - (r - l - cnt);
        return query(mid + 1, R, newl, newr, dep + 1, k - cnt);
    }
}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d%d", &N, &M);
    rep(i, 1, N + 1) {
        scanf("%d", &tree[0][i]);
        sorted[i] = tree[0][i];
    }
    sort(sorted + 1, sorted + 1 + N);
    build(1, N, 0);
    int s, t, k;
    rep(i, 0, M) {
        scanf("%d%d%d", &s, &t, &k);
        printf("%d\n", query(1, N, s, t, 0, k));
    }
    return 0;
}

hduoj 3473
有一个正整数序列，给定区间[l,r]，找一个整数x使得

最小，求这个最小值。

首先可以分析得知该x即是[l,r]中的中位数。可以推得
ans=rsum-lsum+midVal*(lcnt-rcnt)。
其中rsum是序列中中位数右侧和，lsum对应其左侧和，lcnt是左侧元素个数，rcnt是右侧个数。
留意：找中位数，转右子树操作，此时的cnt是[l,r]内的位于中位数左侧的个数，要和起来，lsum同。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 1e5 + 5;
int N, M, T;
int tree[20][maxN];
int toLeft[20][maxN];
int sorted[maxN];
// leftSum[d][i] 为d层[1,i]进入左子数元素之和
ll leftSum[20][maxN], sum[maxN];
ll lsum, rsum;
int lcnt, rcnt;

void build(int l, int r, int d) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    int same = mid - l + 1;
    int smid = sorted[mid];
    rep(i, l, r + 1)
        if (tree[d][i] < smid)
            --same;

    int lpos = l, rpos = mid + 1;
    rep(i, l, r + 1) {
        if (tree[d][i] < smid) {
            tree[d + 1][lpos++] = tree[d][i];
            leftSum[d][i] = leftSum[d][i - 1] + tree[d][i];
        } else if (tree[d][i] == smid && same > 0) {
            --same;
            tree[d + 1][lpos++] = tree[d][i];
            leftSum[d][i] = leftSum[d][i - 1] + tree[d][i];
        } else {
            tree[d + 1][rpos++] = tree[d][i];
            leftSum[d][i] = leftSum[d][i - 1];
        }
        toLeft[d][i] = toLeft[d][l - 1] + lpos - l;
    }
    build(l, mid, d + 1);
    build(mid + 1, r, d + 1);
}

int query(int L, int R, int l, int r, int d, int k) {
    if (l == r) return tree[d][l];
    
    int mid = (L + R) >> 1;
    int cnt = toLeft[d][r] - toLeft[d][l - 1];
    if (cnt >= k) {
        int newl = L + toLeft[d][l - 1] - toLeft[d][L - 1];
        int newr = newl + cnt - 1;
        return query(L, mid, newl, newr, d + 1, k);
    } else {
        int newr = r + toLeft[d][R] - toLeft[d][r];
        int newl = newr - (r - l - cnt);

        lcnt += cnt;
        lsum += leftSum[d][r] - leftSum[d][l - 1];

        return query(mid + 1, R, newl, newr, d + 1, k - cnt);
    }

}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d", &T);
    rep(i, 1, T + 1) {
        sum[0] = 0;

        scanf("%d", &N);
        rep(i, 1, N + 1) {
            scanf("%d", &tree[0][i]);
            sorted[i] = tree[0][i];
            sum[i] = sum[i - 1] + sorted[i];
        }
        sort(sorted + 1, sorted + 1 + N);
        build(1, N, 0);

        printf("Case #%lld:\n", i);
        scanf("%d", &M);
        while (M--) {
            int s, t;
            scanf("%d%d", &s, &t);
            ++s; ++t;
            lcnt = rcnt = 0;
            lsum = 0;
            int mid = (s + t) / 2 - s + 1;
            int midVal = query(1, N, s, t, 0, mid);
            rcnt = t - s + 1 - lcnt;
            rsum = sum[t] - sum[s - 1] - lsum;
            ll ans = rsum - lsum + midVal * (lcnt - rcnt);
            printf("%lld\n", ans);
        }
        puts("");
    }
    return 0;
}