思路：將n個數的序列不斷劃分拓哺，根節(jié)點是原序列勇垛，左子樹是原序列排序后較小的一半，右子樹是另一半士鸥。留意闲孤，子數中的元素的相對位置是和父親序列一樣的，見圖烤礁，這部分參考了這個博客：
其中讼积，紅色標記是進入左子樹的元素。
首先脚仔，數組序號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循環(huán)新加入的往左的數量。
查詢下標計算比較關鍵。[L,R]是大區(qū)間眠屎，[l,r]是查詢的小區(qū)間剔交，先查詢[l,r]內有前往左子樹的元素數量，記為cnt改衩，若cnt>=k岖常，意味著第k大數必然在左子樹，否則去了右子樹葫督。
不論去哪竭鞍，都要重新計算查詢的區(qū)間。結合圖分析計算
若往左橄镜。新的左起始下標應該是L+toLeft[dep][l-1]-toLeft[dep][L-1]笼蛛，即seg1區(qū)間內往左走的元素，相當于越過seg1前往左子樹元素后蛉鹿，才是[l,r]區(qū)間里往左走的元素起始點滨砍。新的右限自然是newl+cnt-1。
若往右妖异。新的右起始點也應該去除[r, R]區(qū)間往左走的元素干擾惋戏，所以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是大區(qū)間 l,r是查詢區(qū)間,查詢第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
有一個正整數序列，給定區(qū)間[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;
}
