Problema implementando segtree

Ciao, sto avendo qualche problema durante l’implementazione del segtree. Premetto che il segmentation tree è una struttura dati completamente nuova per me, e che per costruire il mio programma ho preso spunto (molto fortemente) dall’esempio fornito da geeksforgeeks

g_a è una copia globale della serie numerica originale, mente tree è il segmentation tree

eseguendo il programma ricevo 0/100 con molti casi che superano il tempo limite di esecuzione

Allego il codice:

vector<long long> tree;
vector<long long> g_a;



// A utility function to get the middle index from corner indexes.
int getMid(int s, int e) { return s + (e - s) / 2; }

/* si, ss and se are same as getSumUtil()
    i --> index of the element to be updated. This index is
            in the input array.
diff --> Value to be added to all nodes which have i in range */
void updateValueUtil(int ss, int se, int i, int diff, int si) {
  // Base Case: If the input index lies outside the range of
  // this segment
  if (i < ss || i > se)
    return;

  // If the input index is in range of this node, then update
  // the value of the node and its children
  tree[si] = tree[si] + diff;
  if (se != ss) {
    int mid = getMid(ss, se);
    updateValueUtil(ss, mid, i, diff, 2 * si + 1);
    updateValueUtil(mid + 1, se, i, diff, 2 * si + 2);
  }
}

// The function to update a value in input array and segment tree.
// It uses updateValueUtil() to update the value in segment tree
void set_range(int l, int r, long long x) {
  for (int i=l; i<r; i++) {
    // Get the difference between new value and old value
    long long diff = x - g_a[i];

    // Update the value in array
    g_a[i] = x;

    // Update the values of nodes in segment tree
    updateValueUtil(0, g_a.size() - 1, i, diff, 0);
  }
}

void add(int l, int r, long long x) {

  for (int i=l; i<r; i++) {
    // Get the difference between new value and old value
    long long diff = x;
    // Update the value in array
    g_a[i] = g_a[i] + diff;
    // Update the values of nodes in segment tree
    updateValueUtil(0, g_a.size() - 1, i, diff, 0);
  }

}

/* si --> Index of current node in the segment tree. Initially
            0 is passed as root is always at index 0
    ss & se --> Starting and ending indexes of the segment represented
                by current node, i.e., st[si]
    qs & qe --> Starting and ending indexes of query range 
*/
long long getSumUtil(int ss, int se, int qs, int qe, int si) {
  // If segment of this node is a part of given range, then return
  // the sum of the segment
  if (qs <= ss && qe >= se)
    return tree[si];

  // If segment of this node is outside the given range
  if (se < qs || ss > qe)
    return 0;

  // If a part of this segment overlaps with the given range
  int mid = getMid(ss, se);
  return getSumUtil(ss, mid, qs, qe, 2 * si + 1) +
         getSumUtil(mid + 1, se, qs, qe, 2 * si + 2);
}

// Return sum of elements in range from index qs (query start)
// to qe (query end). It mainly uses getSumUtil()
long long get_sum(int qs, int qe) {
  return getSumUtil(0, g_a.size() - 1, qs, qe-1, 0);
}

// A recursive function that constructs Segment Tree for array[ss..se].
// si is index of current node in segment tree st
long long constructSTUtil(int ss, int se, int si) {
  // If there is one element in array, store it in current node of
  // segment tree and return
  if (ss == se) {
    tree[si] = g_a[ss];
    return g_a[ss];
  }

  // If there are more than one elements, then recur for left and
  // right subtrees and store the sum of values in this node
  int mid = getMid(ss, se);
  tree[si] = constructSTUtil(ss, mid, si * 2 + 1) +
           constructSTUtil(mid + 1, se, si * 2 + 2);
  return tree[si];
}

/* Function to construct segment tree from given array. This function
allocates memory for segment tree and calls constructSTUtil() to
fill the allocated memory */
void init(vector<long long> a) {
  g_a = a;
  // Height of segment tree
  int x = (int)(ceil(log2(a.size())));
  // Maximum size of segment tree
  int max_size = 2 * (int)pow(2, x) - 1;
  // Allocate memory
  tree.resize(max_size);
  // Fill the allocated memory st
  constructSTUtil(0, a.size() - 1, 0);
}


long long get_min(int l, int r) {
  // NOT IMPLEMENTED
  // long long min = get_sum(l, r);
  // for (int i = l; i <= r; i++)
    // min = min < g_a[i] ? min : g_a[i];
  return -12345;
}

int lower_bound(int l, int r, long long x) {
  // NOT IMPLEMENTED
  return -12345;
}

Quando hai sia range update che range query, per mantenere complessità logaritmica serve la lazy propagation. Ti consiglio questa spiegazione del segment da cp-algorithms (che è in generale un buon posto per cercare spiegazioni).

Se invece fossi interessato al segment iterativo, puoi leggere Efficient and easy segment tree su codeforces, ma nota che la versione ricorsiva è più semplice se ti serve lazy propagation.

Detto ciò, un altro paio di consigli:

  • (secondo me) la funzione getMid è overkill, ma se proprio ci tieni puoi usare std::midpoint che fa esattamente la stessa cosa
  • evita di usare i floating point quando possibile, puoi sostituire (int)pow(2, x) con (1 << x), dove << è bitwise left shift (n << m è n * 2^m, con n e m interi)
  • in questo problema il tuo segment deve supportare tante query di tipo diverso: è conveniente creare una struct node che contenga tutte le informazioni di cui hai bisogno

Perfetto, intanto ti ringrazio per la spiegazione e per i consigli.
Appena possibile cercherò di mettere in pratica quello che mi hai detto.
Se trovo altre difficoltà, continuerò a scrivere qui.

Ciao, sono riuscito ad implementare la soluzione tramite lazy loading, ma soltanto per calcolare le somme. Quale potrebbe essere un modo per rendere la struttura dati adatta a rispondere alle altre query?

Dipende da che query, ma il concetto e’ sempre quello.
Basta riuscire a capire come si aggiorna il valore di una query su un range facendo un update,
per esempio se hai range sum e max query, fare +x su un range, se il massimo era m, diventa m+x.
Ovviamente non puo fare di tutto (ma puoi comunque farci molto).

Penso di aver fatto qualche progresso:

In ogni caso adesso ho uno strano errore… malloc() corrupted top size

PS; per ora sto cercando di implementare solo set e add