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

AGGIORNAMENTO:

Ho riprovato a prendere in mano in problema dopo averlo lasciato stare per un po’ (periodo di vacanza).
Credevo di essere riuscito a implementare la lazy propagation nel modo corretto, ma continuo ad avere problemi di tempo. Codice a seguire. Per ora ho implementato solo la funzione add e get sum

(questo è solo un pezzo del codice)

struct Nodo {
	int left, right;
	long long lazySum;
	long long value;
	// default constructor
	Nodo() : left(0), right(0), lazySum(0), value(0) {}
};


vector<Nodo> segtree;

void build(int i, int l, int r, vector<long long> a) {
    // l=sinistra (left), r=destra (right), i=indice dell'array segtree
    if (l > r) return;
	
	if (l == r) {
		// foglia
        segtree[i].value = a[l];
		segtree[i].left = segtree[i].right = l;
        return;
    }

	// nodo intermedio, setto gli index di destra e sinistra
	segtree[i].left = l;
	segtree[i].right = r;

    int m = (l + r) / 2;

    build(i*2 + 1, l, m, a);
    build(i*2 + 2, m + 1, r, a);
	
	// aggiorno il valore del nodo
    segtree[i].value = segtree[i*2 + 1].value + segtree[i * 2 + 2].value;
}

void init(vector<long long> a) {
	int size=1;
	while (size < a.size()) size *= 2;
  	segtree.resize(2*size-1);
  	build(0, 0, a.size()-1, a);
}

void checkForLazyness(int i) {
	if (segtree[i].lazySum != 0) {
		// c'è un update registrato, lo applico
        segtree[i].value += (segtree[i].right-segtree[i].left+1)*segtree[i].lazySum;
		// controllo che non sia una foglia (non ha figli)
        if (segtree[i].left != segtree[i].right) {
            segtree[i*2+1].lazySum += segtree[i].lazySum;
            segtree[i*2+2].lazySum += segtree[i].lazySum;
        }
        // reset della lazy sum sul nodo corrente
		segtree[i].lazySum = 0;
    }
}

long long get_sum(int l, int r) {
	return get_sum(0, l, r-1);
}

long long get_sum(int i, int l, int r) {
  
    // controllo di essere sempre nel range corretto di indexs
    if (segtree[i].left>r || segtree[i].right<l)
        return 0;
		
	// Siamo totalmente nel range, tutto il nodo è da considerare
    if (segtree[i].left>=l && segtree[i].right<=r)
        return segtree[i].value;
  
	checkForLazyness(i);
    
  
    // soltanto parte del nodo è nel range: occorre la ricorsione
    // int mid = (segtree[i].left + segtree[i].right)/2;
    return get_sum(2*i+1, l, r) + get_sum(2*i+2, l, r);
}

void add(int l, int r, long long x) {
	add(0, l, r-1, x);
}

void add(int i, int l, int r, long long x) {
	// controllo di essere sempre nel range corretto di indexs
    if (segtree[i].left>r || segtree[i].right<l)
        return;
  
	checkForLazyness(i);
    // Siamo totalmente nel range, tutto il nodo è da considerare
    if (segtree[i].left>=l && segtree[i].right<=r) {
        // aggiungo la differenza al nodo
        segtree[i].value += (segtree[i].right-segtree[i].left+1)*x;
        // controllo che non sia una foglia
        if (segtree[i].left != segtree[i].right) {
			// aggiorno la lazy sum dei figli
            segtree[i * 2 + 1].lazySum += x;
            segtree[i * 2 + 2].lazySum += x;
        }
        return;
	}

	// soltanto parte del nodo è nel range: occorre la ricorsione
	int mid = (segtree[i].left + segtree[i].right)/2;
	add(2*i+1, l, r, x);
	add(2*i+2, l, r, x);
  
	// aggiorno il valore del nodo
	segtree[i].value = segtree[i*2 + 1].value + segtree[i * 2 + 2].value;
}

prova a fare segtree.resize(4*size+1) invece di 2*size-1.
also, in get_sum(i,l,r) defi fare checkForLazyness prima del secondo if