la recherche d'une structure de données pour effectuer la mise à jour des éléments de gamme efficacement

Question

J'ai actuellement la structure des données suivantes:

class DataStructure { 
public: 
    DataStructure(int n) : m_data(n, 0) { 
    } 

    void update(int i, int j, int value) { 
    for (int k = i; k <= j; ++k) { 
     m_data[k] = max(m_data[k], value); 
    } 
    } 

    void reset(int i) { 
    m_data[i] = 0; 
    } 

    int query(int i) { 
    return m_data[i]; 
    } 

private: 
    vector<int> m_data; 
}; 

donc ce qu'il fait est assez simple:

• Dans un premier temps, il est un vecteur de n entiers initialisés à zéro. La mise à jour (i, j, valeur) met à jour les éléments dans la plage [i, j] pour qu'ils soient le maximum de la valeur donnée et de leur valeur actuelle respective. La valeur donnée est dans la plage de [0, n]. Reset (i) réinitialise la valeur à l'index i à 0.
• La requête (i) renvoie la valeur à l'index i.

J'ai besoin d'effectuer n mises à jour, n réinitialisations et n opérations de requête. Actuellement, ce code prend l'heure O (n * n), en raison de l'opération de mise à jour étant O (n) en général. Je me demande s'il y a des façons intelligentes d'améliorer ce temps O (n * log n) (ou mieux) pour n mises à jour, n réinitialisations et n opérations de requête, tout en conservant la complexité de l'espace O (n)?

Answer 1

Merci pour @qwertman pour l'explication est ici un algorithme qui devrait fonctionner

#include <iostream> 
#include <cstdio> 
using namespace std; 
#define max(a, b) (a>b?a:b) 
int tree[100005], lazy[100005]; 
void init(int idx, int l, int r){ 
    if(l>r) 
     return ; 
    if(l==r){ 
     tree[idx] = 0; 
     lazy[idx] = -1; 
    } 
    else { 
     tree[idx] = 0; 
     lazy[idx] = -1; 
     int mid = (l+r)/2; 
     init(2*idx, l, mid); 
     init(2*idx+1, mid+1, r); 
    } 
} 
// l and r is for internal use the range a-b has to be updated 
void update(int idx, int l, int r, int a, int b, int val, bool isReset){ 
    if(l>r || b<l || a>r){ 
     return; 
    } 
    // printf("idx=%d l=%d r=%d a=%d b=%d val=%d\n",idx,l,r,a,b,val); 
    if(lazy[idx] != -1){ 
     tree[idx] = max(tree[idx], lazy[idx]); 
     lazy[2*idx] = max(lazy[2*idx], lazy[idx]); 
     lazy[2*idx+1] = max(lazy[2*idx+1], lazy[idx]); 
     lazy[idx] = -1; 
    } 
    if(l>=a && r<=b){ 
     // printf("updating\n"); 
     tree[idx] = max(tree[idx], val); 
     if(isReset){ 
      tree[idx] = val; 
     } 
     lazy[2*idx] = max(lazy[2*idx], val); 
     lazy[2*idx+1] = max(lazy[2*idx+1], val); 
     lazy[idx] = -1; 
    } 
    else { 
     int mid = (l+r)/2; 
     update(2*idx, l, mid, a, b, val, isReset); 
     update(2*idx+1, mid+1, r, a, b, val, isReset); 
     tree[idx] = max(tree[2*idx], tree[2*idx+1]); 
    } 
} 
int query(int idx, int l, int r, int a){ 
    if(l>r || a<l || a>r){ 
     return -1; 
    } 
    // printf("idx=%d l=%d r=%d a=%d\n",idx,l,r,a); 
    if(lazy[idx] != -1){ 
     tree[idx] = max(tree[idx], lazy[idx]); 
     lazy[2*idx] = max(lazy[2*idx], lazy[idx]); 
     lazy[2*idx+1] = max(lazy[2*idx+1], lazy[idx]); 
     lazy[idx] = -1; 
    } 
    if(l==a && r==a){ 
     // printf("----l=%d r=%d a=%d tree=%d\n",l,r,a,tree[idx]); 
     return tree[idx]; 
    } 
    else { 
     int mid = (l+r)/2; 
     int left = query(2*idx, l, mid, a); 
     int right = query(2*idx+1, mid+1, r, a); 
     return max(left, right); 
    } 
} 
int main() { 
    // initializing everything to 0 
    init(1, 1, 10); 

    // updating range 1-4 with value 7 
    update(1, 1, 10, 1, 4, 7, false); 

    // query for 3 should result in 7 
    cout << query(1, 1, 10, 3) << endl; 

    // updating 3-3 with value 9 
    update(1, 1, 10, 3, 3, 9, false); 

    // should give 9 
    cout << query(1, 1, 10, 3) << endl; 

    // isReset is set to true, so the function will do a hard reset 
    update(1, 1, 10, 3, 3, 0, true); 

    // should give 0 
    cout << query(1, 1, 10, 3) << endl; 
    return 0; 
} 

vous pouvez exécuter ce code à http://ideone.com/Mkp4dQ
quelques liens utiles pour l'arbre segment apprentissage à la propagation paresseuse
hackerearth Geeksforgeeks