如何释放指针树全部内存？可持久化线段树内存优化方案

最近在做Codechef上的GIVEAWAY问题时，我用指针实现了可持久化线段树，结果遇到了头疼的内存释放问题——折腾了半天内存根本没降多少，最后换成数组式实现才彻底解决，分享下我的经历和解决方案：

指针实现的坑：内存释放不彻底 #

我最初的节点结构是这样的：

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

然后用一个指针数组保存各个版本的根节点：

node *version[maxn];

当需要重新构建线段树时，我想着循环delete version[i]就能释放之前的内存，结果内存占用只从1000MB左右降到960MB——这明显不对啊！后来才反应过来：delete根节点只会释放根节点本身的内存，它的左右子节点、孙子节点这些都还留在堆里，相当于只砍了树的根，整个树的枝干都没清理，自然内存泄漏严重。

要是手动写递归释放函数呢？理论上可行，但可持久化线段树不同版本之间是共享节点的，递归释放很可能会把其他版本还在使用的节点给删掉，反而引发更严重的崩溃问题，完全得不偿失。

最优方案：换成数组式可持久化线段树 #

思来想去，直接放弃指针实现，改用数组式（静态）的可持久化线段树才是正道。这种方式不用指针，靠数组索引来关联节点，根本不需要手动管理内存，内存占用还能大幅降低。

完整的数组实现代码 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 5;
const int MAX_NODE = 20 * MAXN; // 根据问题规模估算足够的节点数

// 数组式节点，用索引代替指针
struct Node {
    int val;
    int left, right; // 左右子节点的数组索引，0表示空
} tree[MAX_NODE];

int version[MAXN]; // 每个版本的根节点索引
int cnt; // 全局节点计数器，用来分配新节点

// 构建初始线段树
int build(int l, int r) {
    int cur = ++cnt;
    if (l == r) {
        tree[cur].val = 0; // 根据问题需求设置初始值
        tree[cur].left = tree[cur].right = 0;
        return cur;
    }
    int mid = (l + r) >> 1;
    tree[cur].left = build(l, mid);
    tree[cur].right = build(mid + 1, r);
    tree[cur].val = tree[tree[cur].left].val + tree[tree[cur].right].val;
    return cur;
}

// 更新操作，基于旧版本生成新版本
int update(int prev, int l, int r, int pos, int val) {
    int cur = ++cnt;
    tree[cur] = tree[prev]; // 复制旧节点的所有信息
    if (l == r) {
        tree[cur].val += val;
        return cur;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) {
        tree[cur].left = update(tree[prev].left, l, mid, pos, val);
    } else {
        tree[cur].right = update(tree[prev].right, mid + 1, r, pos, val);
    }
    tree[cur].val = tree[tree[cur].left].val + tree[tree[cur].right].val;
    return cur;
}

// 查询指定版本的区间和
int query(int root, int l, int r, int ql, int qr) {
    if (qr < l || ql > r) return 0;
    if (ql <= l && r <= qr) return tree[root].val;
    int mid = (l + r) >> 1;
    return query(tree[root].left, l, mid, ql, qr) + query(tree[root].right, mid + 1, r, ql, qr);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cnt = 0;
    int n;
    cin >> n;
    version[0] = build(1, n); // 初始版本
    
    int m;
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            // 更新操作，生成新版本
            int pos, val;
            cin >> pos >> val;
            version[i] = update(version[i-1], 1, n, pos, val);
        } else {
            // 查询操作，可以选择复用旧版本
            int ver, ql, qr;
            cin >> ver >> ql >> qr;
            cout << query(version[ver], 1, n, ql, qr) << '\n';
            version[i] = version[ver]; // 不需要新节点时直接复用
        }
    }
    return 0;
}

数组式实现的优势 #

• 内存零泄漏：所有节点都在数组中分配，程序结束后会自动释放，完全不用手动管理内存。
• 内存更高效：指针式每个节点要存两个指针（16字节左右），数组式用整数索引（8字节左右），直接省了一半的额外开销，内存占用大幅降低。
• 代码更稳定：不用处理空指针、野指针，也不用纠结递归释放的问题，减少了很多潜在bug。

内容的提问来源于stack exchange，提问作者SinByCos