# Problema implementando segtree

**URL:** <https://forum.olinfo.it/t/problema-implementando-segtree/7421>\
**Category:** Aiuto\
**Created:** [13 Giugno 2022, 1:22pm UTC](https://forum.olinfo.it/t/problema-implementando-segtree/7421 "2022-06-13T13:22:31Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![Enrico\_covili](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/f9ae1b/32.png) [@Enrico\_covili](https://forum.olinfo.it/u/Enrico_covili)\
**Post date:** [13 Giugno 2022, 1:22pm UTC](https://forum.olinfo.it/t/problema-implementando-segtree/7421/1 "2022-06-13T13:22:31Z")

</div>

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](https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/)

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:

```auto
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;
}

```

---

<div class="post-metadata">

**Author:** ![lorenzoferrari](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lorenzoferrari/32/683_2.png) [@lorenzoferrari](https://forum.olinfo.it/u/lorenzoferrari)\
**Post date:** [13 Giugno 2022, 3:06pm UTC](https://forum.olinfo.it/t/problema-implementando-segtree/7421/2 "2022-06-13T15:06:02Z")

</div>

Quando hai sia range update che range query, per mantenere complessità logaritmica serve la lazy propagation. Ti consiglio [questa](https://cp-algorithms.com/data_structures/segment_tree.html) 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](https://codeforces.com/blog/entry/18051) 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](https://en.cppreference.com/w/cpp/numeric/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

---

<div class="post-metadata">

**Author:** ![Enrico\_covili](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/f9ae1b/32.png) [@Enrico\_covili](https://forum.olinfo.it/u/Enrico_covili)\
**Post date:** [13 Giugno 2022, 4:15pm UTC](https://forum.olinfo.it/t/problema-implementando-segtree/7421/3 "2022-06-13T16:15:55Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Enrico\_covili](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/f9ae1b/32.png) [@Enrico\_covili](https://forum.olinfo.it/u/Enrico_covili)\
**Post date:** [14 Giugno 2022, 3:17pm UTC](https://forum.olinfo.it/t/problema-implementando-segtree/7421/4 "2022-06-14T15:17:14Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![MyK\_00L](https://forum.olinfo.it/user_avatar/forum.olinfo.it/myk_00l/32/3000_2.png) [@MyK\_00L](https://forum.olinfo.it/u/MyK_00L)\
**Post date:** [15 Giugno 2022, 7:15am UTC](https://forum.olinfo.it/t/problema-implementando-segtree/7421/5 "2022-06-15T07:15:30Z")

</div>

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](https://codeforces.com/blog/entry/57319)).

---

<div class="post-metadata">

**Author:** ![Enrico\_covili](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/f9ae1b/32.png) [@Enrico\_covili](https://forum.olinfo.it/u/Enrico_covili)\
**Post date:** [15 Giugno 2022, 9:29am UTC](https://forum.olinfo.it/t/problema-implementando-segtree/7421/6 "2022-06-15T09:29:33Z")

</div>

Penso di aver fatto qualche progresso:

> **[\#include #include #include #include](https://pastebin.com/4hpM438r)**
>
> Pastebin.com is the number one paste tool since 2002. Pastebin is a website where you can store text online for a set period of time.

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

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

---

<div class="post-metadata">

**Author:** ![Enrico\_covili](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/e/f9ae1b/32.png) [@Enrico\_covili](https://forum.olinfo.it/u/Enrico_covili)\
**Post date:** [16 Luglio 2022, 8:17am UTC](https://forum.olinfo.it/t/problema-implementando-segtree/7421/7 "2022-07-16T08:17:30Z")

</div>

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)

```auto
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;
}

```

---

<div class="post-metadata">

**Author:** ![MyK\_00L](https://forum.olinfo.it/user_avatar/forum.olinfo.it/myk_00l/32/3000_2.png) [@MyK\_00L](https://forum.olinfo.it/u/MyK_00L)\
**Post date:** [23 Luglio 2022, 11:24am UTC](https://forum.olinfo.it/t/problema-implementando-segtree/7421/8 "2022-07-23T11:24:23Z")

</div>

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