优化矩阵乘法线段树查询函数，解决内存泄漏问题

核心问题是原代码中matrix_mult每次调用都动态分配Matrix对象，递归查询时无法追踪释放这些对象，导致内存泄漏。下面给出两种高效修复方案，完全避免动态内存分配：

方案一：原地矩阵乘法 + 值返回查询函数 #

1. 重构matrix_mult为原地修改版本 #

将矩阵乘法改为接受输入矩阵的const引用，结果写入第三个引用参数，彻底消除动态分配：

#include <cassert>

class Matrix {
public:
    using matrix_type = long long; // 根据实际类型调整
    int rows, cols;
    matrix_type* data;

    // 构造、析构等原有成员...

    // 新增const版本的operator()，支持访问const矩阵
    const matrix_type& operator()(int i, int j) const {
        return data[i * cols + j];
    }

    matrix_type& operator()(int i, int j) {
        return data[i * cols + j];
    }

    // 重构后的矩阵乘法：无动态分配
    static void matrix_mult(const Matrix& a, const Matrix& b, Matrix& result) {
        // 前置检查：确保矩阵尺寸合法
        assert(a.cols == b.rows);
        assert(result.rows == a.rows && result.cols == b.cols);

        // 清零结果矩阵
        for (int i = 0; i < result.rows * result.cols; ++i) {
            result.data[i] = 0;
        }

        const matrix_type delimiter = 100000000;
        for (int i = 0; i < a.rows; ++i) {
            for (int j = 0; j < b.cols; ++j) {
                matrix_type sum = 0;
                for (int k = 0; k < a.cols; ++k) {
                    sum += a(i, k) * b(k, j);
                }
                result(i, j) = sum % delimiter;
            }
        }
    }
};

2. 修改query函数为值返回 #

递归查询时直接返回矩阵对象，利用C++返回值优化(RVO)减少拷贝开销，同时避免动态内存：

class Segtree {
private:
    struct Node { Matrix* matrix; };
    Node* seg;
    Matrix* identity_matrix; // 单位矩阵为单例对象

public:
    Matrix query(int a, int b, int p, int l, int r) {
        // 区间无交集：返回单位矩阵
        if (b < l || r < a) {
            return *identity_matrix;
        }

        // 当前区间完全包含在查询区间内：返回节点存储的矩阵
        if (a <= l && r <= b) {
            return *seg[p].matrix;
        }

        int m = (l + r) / 2;
        Matrix left = query(a, b, 2 * p, l, m);
        Matrix right = query(a, b, 2 * p + 1, m + 1, r);

        // 优化：如果其中一个是单位矩阵，直接返回另一个，跳过乘法
        auto is_identity = [this](const Matrix& mat) {
            if (mat.rows != identity_matrix->rows || mat.cols != identity_matrix->cols) return false;
            for (int i = 0; i < mat.rows * mat.cols; ++i) {
                if (mat.data[i] != identity_matrix->data[i]) return false;
            }
            return true;
        };
        if (is_identity(left)) return right;
        if (is_identity(right)) return left;

        // 合并左右结果
        Matrix result(left.rows, right.cols);
        Matrix::matrix_mult(left, right, result);
        return result;
    }
};

方案二：输出参数式查询（大矩阵场景更高效） #

如果矩阵尺寸较大，可进一步优化为传入输出参数，减少临时对象的创建：

修改后的query函数 #

void Segtree::query(int a, int b, int p, int l, int r, Matrix& result) {
    if (b < l || r < a) {
        result = *identity_matrix;
        return;
    }

    if (a <= l && r <= b) {
        result = *seg[p].matrix;
        return;
    }

    int m = (l + r) / 2;
    Matrix left, right;
    query(a, b, 2 * p, l, m, left);
    query(a, b, 2 * p + 1, m + 1, r, right);

    // 单位矩阵优化（同方案一的is_identity逻辑）
    auto is_identity = [this](const Matrix& mat) {
        if (mat.rows != identity_matrix->rows || mat.cols != identity_matrix->cols) return false;
        for (int i = 0; i < mat.rows * mat.cols; ++i) {
            if (mat.data[i] != identity_matrix->data[i]) return false;
        }
        return true;
    };
    if (is_identity(left)) {
        result = right;
        return;
    }
    if (is_identity(right)) {
        result = left;
        return;
    }

    // 确保结果矩阵尺寸正确
    if (result.rows != left.rows || result.cols != right.cols) {
        result = Matrix(left.rows, right.cols);
    }
    Matrix::matrix_mult(left, right, result);
}

调用方式 #

Matrix result;
segtree.query(query_a, query_b, 1, 0, max_idx, result);

关键优化点 #

• 彻底移除new操作，所有矩阵对象通过栈或成员变量管理，完全避免内存泄漏
• 增加单位矩阵判断，跳过不必要的乘法计算
• 实现const版本的operator()，保证const矩阵的访问合法性

内容的提问来源于stack exchange，提问作者Thiago Roberto magalhaẽs