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