Problème de structure de données

Question

Étant donné une séquence d'entiers, il existe un certain nombre de requêtes. Chaque requête a une portée [l, r], et vous permet de trouver la médiane de la fourchette donnée [l, r]

Le nombre de requêtes peut être aussi grand que 100 000 La longueur de la séquence peut être aussi grand que 100 000

Je me demande s'il y a une structure de données peut prendre en charge cette requête

---

ma solution:

Je consulte mon partenaire aujourd'hui et il demande d'utiliser l'arbre de partition.

Nous pouvons construire un arbre de partition dans nlog (n) et répondre à chaque requête dans le journal (n)

L'arbre de partition est en fait le processus de tri fusion, mais pour chaque nœud de l'arbre, il enregistre le nombre d'entiers qui vont à la sous-arborescence gauche. Ainsi, nous pouvons utiliser cette information pour traiter la requête.

voici mon code:

Ce programme est de trouver x dans un intervalle donné [l, r], qui réduisent au minimum l'équation suivante.

alt text http://acm.tju.edu.cn/toj/3556_01.jpg

Explication:

suivants enregistre la séquence

pos enregistre la position après tri

ind enregistre l'index

CNTL enregistre le nombre d'entiers qui aller à l'arbre de gauche dans une plage donnée

#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
#define N 100008 
typedef long long LL; 
int n, m, seq[N], ind[N], pos[N], next[N]; 
int cntL[20][N]; 
LL sum[20][N], sumL, subSum[N]; 

void build(int l, int r, int head, int dep) 
{ 
    if (l == r) 
    { 
     cntL[dep][l] = cntL[dep][l-1]; 
     sum[dep][l] = sum[dep][l-1]; 
     return ; 
    } 
    int mid = (l+r)>>1; 
    int hl = 0, hr = 0, tl = 0, tr = 0; 
    for (int i = head, j = l; i != -1; i = next[i], j++) 
    { 
     cntL[dep][j] = cntL[dep][j-1]; 
     sum[dep][j] = sum[dep][j-1]; 
     if (pos[i] <= mid) 
     { 
      next[tl] = i; 
      tl = i; 
      if (hl == 0) hl = i; 
      cntL[dep][j]++; 
      sum[dep][j] += seq[i]; 
     } 
     else 
     { 
      next[tr] = i; 
      tr = i; 
      if (hr == 0) hr = i; 
     } 
    } 
    next[tl] = -1; 
    next[tr] = -1; 
    build(l, mid, hl, dep+1); 
    build(mid+1, r, hr, dep+1); 
} 

int query(int left, int right, int ql, int qr, int kth, int dep) 
{ 
    if (left == right) 
    { 
     return ind[left]; 
    } 
    int mid = (left+right)>>1; 
    if (cntL[dep][qr] - cntL[dep][ql-1] >= kth) 
    { 
     return query(left, mid, left+cntL[dep][ql-1]-cntL[dep][left-1], left+cntL[dep][qr]-cntL[dep][left-1]-1, kth, dep+1); 
    } 
    else 
    { 
     sumL += sum[dep][qr]-sum[dep][ql-1]; 
     return query(mid+1, right, mid+1+ql-left-(cntL[dep][ql-1]-cntL[dep][left-1]), mid+qr+1-left-(cntL[dep][qr]-cntL[dep][left-1]), \ 
       kth-(cntL[dep][qr]-cntL[dep][ql-1]), dep+1); 
    } 
} 

inline int cmp(int x, int y) 
{ 
    return seq[x] < seq[y]; 
} 

int main() 
{ 
    int ca, t, i, j, middle, ql, qr, id, tot; 
    LL ans; 
    scanf("%d", &ca); 
    for (t = 1; t <= ca; t++) 
    { 
     scanf("%d", &n); 
     subSum[0] = 0; 
     for (i = 1; i <= n; i++) 
     { 
      scanf("%d", seq+i); 
      ind[i] = i; 
      subSum[i] = subSum[i-1]+seq[i]; 
     } 
     sort(ind+1, ind+1+n, cmp); 
     for (i = 1; i <= n; i++) 
     { 
      pos[ind[i]] = i; 
      next[i] = i+1; 
     } 
     next[n] = -1; 
     build(1, n, 1, 0); 
     printf("Case #%d:\n", t); 
     scanf("%d", &m); 
     while (m--) 
     { 
      scanf("%d%d", &ql, &qr); 
      ql++, qr++; 
      middle = (qr-ql+2)/2; 
      sumL= 0; 
      id = query(1, n, ql, qr, middle, 0); 
      ans = subSum[qr]-subSum[ql-1]-sumL; 
      tot = qr-ql+1; 
      ans = ans-(tot-middle+1)*1ll*seq[id]+(middle-1)*1ll*seq[id]-sumL; 
      printf("%lld\n", ans); 
     } 
     puts(""); 
    } 
} 

Answer 1

Ceci est appelé le problème Range Median Query. Le document suivant pourrait être pertinent: Towards Optimal Range Medians. (Lien gratuit, merci à belisarius).

De l'abstrait du papier:

Nous considérons le problème suivant: Étant donné un tableau non trié d'éléments n, et une séquence d'intervalles dans le tableau , calculer la médiane dans chacun des les sous-matrices définies par les intervalles . Nous décrivons un algorithme simple qui nécessite O (nlogk + klogn) temps pour répondre k de telles requêtes médianes. Ceci améliore les algorithmes précédents par un facteur logarithmique et correspond à une borne inférieure de comparaison pour k = O (n). La complexité de l'espace de notre algorithme simple est O (nlogn) dans le modèle de machine pointeur , et O (n) dans le modèle RAM .Dans ce dernier modèle, une structure de données spatiales O (n) plus peut être construite en O (nlogn) temps où le temps par requête est réduit à O (logn/loglogn). Nous donnons aussi variantes dynamiques efficaces des deux structures de données, la réalisation de O (log^2n) temps de requête en utilisant l'espace O (nlogn) dans le modèle de comparaison et O ((log n/loglogn)^2) temps de requête à l'aide O (nlogn/loglogn) espace dans le modèle RAM , et montrent que dans le modèle cellule-sonde , toute structure de données prend en charge les mises à jour dans O (log^O (1) n) temps doit avoir Ω (logn/loglogn) heure de la requête.

Notre approche généralise naturellement gamme dimension supérieure médiane problèmes, où les positions des éléments et gammes de requête multidimensionnels-il réduit une gamme médiane requête à un nombre logarithmique de la plage de comptage requêtes.

Bien sûr, vous pouvez prétraiter tout le tableau en O (n^3) temps (ou peut-être même O (n^2logn) temps) et O (n^2) d'espace pour être en mesure de revenir à la médiane en O (1) fois.

Des contraintes supplémentaires peuvent aider à simplifier la solution. Par exemple, savons-nous que r-l sera inférieur à une constante connue? etc ...