Search code examples
c++pointersstructsegment-tree

How to free all the memory in a tree of pointers

I'm coding a persistent segment tree for the following problem on Codechef: https://www.codechef.com/problems/GIVEAWAY, and my struct for the node looks like this:

struct node {
    int val;
    node *left, *right;
    node (int val, node *left, node *right) : val(val), left(left), right(right) {};
};

I have an array of pointers called version, defined like this:

node *version[maxn];

In my code, I want to build the segment tree from scratch, but I want to free the previously allocated memory. I'm not sure how to do this. I've tried doing something like

for (int i = 1; i <= N; i++) {
        delete version[i];
    }

However when I submit, I don't seem to have reduced memory usage by a lot. Earlier it showed about 1000mb, but now it shows 960mb. I think it is because I haven't freed a lot of memory, because there is an entire tree of pointers. But I'm not sure how to free all of them.

This is the rest of my code, if you want to refer to it. 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <stdio.h>
#include <queue>
#include <set>
#include <list>
#include <cmath>
#include <assert.h>
#include <bitset>
#include <cstring>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip> //cout << setprecision(node) << fixed << num
#include <stack>
#include <sstream>


#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
typedef std::pair <int, int> ii;
typedef std::vector <int> vi;
typedef std::vector <ll> vll;
typedef std::vector <ld> vld;

const int INF = int(1e9);
const ll INF64 = ll(1e18);
const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
using namespace std;
const int maxn = (int)5e5+10;
int A[maxn], N;

struct node {
    int val;
    node *left, *right;
    node (int val, node *left, node *right) : val(val), left(left), right(right) {};
    //~node () { delete left; delete right; }
};

#define null new node (0, NULL, NULL);

node *version[maxn];

void update(node *prev, node *curr, int L, int R, int idx, int val) {
    if (L == R) {
        assert(idx == L);
        curr->val = val;
    }
    else {
        int mid = (L+R)/2;
        if (idx <= mid) {
            curr->right = prev->right;
            curr->left = null;
            update(prev->left, curr->left, L, mid, idx, val);
        }
        else {
            curr->left = prev->left;
            curr->right = null;
            update(prev->right, curr->right, mid+1, R, idx, val);
        }
        curr->val = curr->right->val + curr->left->val;
    }
}

int query(node *curr, int L, int R, int li, int ri) {
    if (ri < L || li > R)
        return 0;
    if (li <= L && ri >= R)
        return curr->val;
    int mid = (L+R)/2;
    return query(curr->left, L, mid, li, ri) + query(curr->right, mid+1, R, li, ri);
}

map <int, int> occ;

void build () {
    //cout << "building..\n";
    vector <ii> V;
    for (int i = 1; i <= N; i++) {
        V.pb(mp(A[i], i));
    }
    sort(all(V));
    occ.clear();
    for (int i = 1; i <= N; i++) {
        delete version[i];
    }
    for (int i = 1; i <= N; i++) {
        ii e = V[i-1];
        occ[e.fi] = i;
        version[i] = null;
        update(version[i-1], version[i], 1, N, e.se, 1);
    }
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &A[i]);
    }
    version[0] = null;
    version[0]->right = version[0];
    version[0]->left = version[0];
    int Q;
    scanf("%d", &Q);
    int block = (int)sqrt(Q);
    for (int i = 0; i < Q; i += block) {
        build();
        vector <ii> updates;
        for (int j = i; j < i+block && j < Q; j++) {
            int type;
            scanf("%d", &type);
            if (type == 0) {
                int a, b, c;
                scanf("%d %d %d", &a, &b, &c);
                auto it = occ.lower_bound(c);
                int cnt = 0;
                if (it != occ.begin()) {
                    it = prev(it);
                    cnt = query(version[it->second], 1, N, a, b);
                }
                int ans = b-a+1-cnt;
                for (ii update : updates) {
                    int idx = update.fi;
                    int pre = A[idx];
                    int nw = update.se;
                    if (a <= idx && idx <= b) {
                        if (nw >= c && pre < c)
                            ans++;
                        if (nw < c && pre >= c)
                            ans--;
                    }
                }
                printf("%d\n", ans);
            }
            else {
                int a, b;
                scanf("%d %d", &a, &b);
                updates.pb(mp(a, b));
            }
        }
        for (ii update : updates) {
            A[update.fi] = update.se;
        }
    }
}

Help would be appreciated a lot!

EDIT:

Well the best solution for this would be to create a persistent segment tree without pointers. I can easily recreate the tree without having to delete all the memory recursively, which is very buggy and annoying to implement, especially since I'm not familiar with pointers. This considerably reduces memory usage.

The new node looks like:

struct node {
    int val;
    int left, right;
    node() : val(0), left(0), right(0) {}
    node(int val) : val(val), left(0), right(0) {}
    node(int val, int l, int r) : val(val), left(l), right(r) {}
};

Here's the implementation if anyone is interested.

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <stdio.h>
#include <queue>
#include <set>
#include <list>
#include <cmath>
#include <assert.h>
#include <bitset>
#include <cstring>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip> //cout << setprecision(node) << fixed << num
#include <stack>
#include <sstream>


#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
typedef std::pair <int, int> ii;
typedef std::vector <int> vi;
typedef std::vector <ll> vll;
typedef std::vector <ld> vld;

const int INF = int(1e9);
const ll INF64 = ll(1e18);
const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
using namespace std;

const int maxn = (int)5e5+10;
int A[maxn], upd[maxn], N;


struct node {
    int val;
    int left, right;
    node() : val(0), left(0), right(0) {}
    node(int val) : val(val), left(0), right(0) {}
    node(int val, int l, int r) : val(val), left(l), right(r) {}
};

node stree[35*maxn];
int root[maxn], nodeCnt = 0;

void update(int old, int &curr, int L, int R, int idx, int val) {
    curr = ++nodeCnt;
    stree[curr] = stree[old];
    if (L == R) {
        assert(idx == L);
        stree[curr].val += val;
    }
    else {
        int mid = (L+R)/2;
        if (idx <= mid) {
            update(stree[old].left, stree[curr].left, L, mid, idx, val);
        }
        else {
            update(stree[old].right, stree[curr].right, mid+1, R, idx, val);
        }
        stree[curr].val = stree[stree[curr].left].val + stree[stree[curr].right].val;
    }
}

int query (int curr, int L, int R, int li, int ri) {
    if (curr == 0 || ri < L || li > R)
        return 0;
    if (li <= L && ri >= R)
        return stree[curr].val;
    int mid = (L+R)/2;
    return query(stree[curr].left, L, mid, li, ri) + query(stree[curr].right, mid+1, R, li, ri);
}

map <int, int> occ;

void build () {
    //cout << "building..\n";
    vector <ii> V;
    for (int i = 1; i <= N; i++) {
        V.pb(mp(A[i], i));
    }
    sort(all(V));
    occ.clear();
    memset(root, 0, sizeof(root));
    for (int i = 0; i <= nodeCnt; i++) {
        stree[i] = node();
    }
    nodeCnt = 0;
    for (int i = 1; i <= N; i++) {
        ii e = V[i-1];
        occ[e.fi] = i;
        update(root[i-1], root[i], 1, N, e.se, 1);
    }
}

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &A[i]);
    }
    int Q;
    scanf("%d", &Q);
    int block = (int)sqrt(Q);
    for (int i = 0; i < Q; i += block) {
        build();
        vector <pair <int, ii>> updates;
        memset(upd, 0, sizeof(upd));
        for (int j = i; j < i+block && j < Q; j++) {
            int type;
            scanf("%d", &type);
            if (type == 0) {
                int a, b, c;
                scanf("%d %d %d", &a, &b, &c);
                auto it = occ.lower_bound(c);
                int cnt = 0;
                if (it != occ.begin()) {
                    it = prev(it);
                    cnt = query(root[it->second], 1, N, a, b);
                }
                int ans = b-a+1-cnt;
                for (pair <int, ii> update : updates) {
                    int idx = update.fi;
                    int pre = A[idx];
                    int nw = update.se.fi;
                    if (upd[idx] != update.se.se) continue;
                    if (a <= idx && idx <= b) {
                        if (nw >= c && pre < c)
                            ans++;
                        if (nw < c && pre >= c)
                            ans--;
                    }
                }
                printf("%d\n", ans);
            }
            else {
                int a, b;
                scanf("%d %d", &a, &b);
                updates.pb(mp(a, mp(b, j)));
                upd[a] = j;
            }
        }
        for (pair <int, ii> update : updates) {
            A[update.fi] = update.se.fi;
        }
    }
}
Solution

  • Simple recurrence:

    void releaseNode(node* n)
{
  if (!n) return;
  releaseNode(n->left);
  releaseNode(n->right);
  delete n;
}

    And an update for the loop itself:

    for (int i = 1; i <= N; i++)
{
  releaseNode(version[i]);
}

    If size of the array version is always a compile-time constant, you can wrap this into a simple function:

    template <size_t N>
void releaseArrayOfNodes(node*(&array)[N])
{
  for (int i = 1; i <= N; i++)
  {
    releaseNode(array[i]);
  }
}

    And then just write:

    releaseArrayOfNodes(version);

    Sorry, I did not notice the fact, that recursive solution may not be an option here, bad day for me today, don't know why.

    You can try iterative solution:

    void releaseNode(node* n)
{
    std::stack<node*> context;
    context.push(n);

    while (!context.empty())
    {
        node* top = context.top();
        context.pop();

        if (top->left != nullptr)
            context.push(top->left);

        if (top->right != nullptr)
            context.push(top->right);

        delete top;
    }
}