C语言 线段树合并 演示代码

线段树（Segment Tree）是一种数据结构，用于高效地支持区间查询和更新操作。在C语言中，线段树通常用来处理数组或区间问题，它将原始的区间操作抽象为树状结构，使得查询和修改操作的时间复杂度可以降低到O(logn)。

合并线段树的操作一般涉及到两个子树的合并，比如在一个区间合并树中，可能需要合并左子树和右子树，然后更新根节点的值。这通常涉及到递归，首先处理子节点，然后将结果合并。

以下是一个简单的线段树合并操作的C语言代码示例，这里假设线段树是二维数组，每个元素代表一个区间的值：

#include <stdio.h>

#define MAXN 100000 // 假设最大节点数

int tree[MAXN << 2]; // 用一个数组存储整个线段树

// 合并两个区间 [l, r] 和 [m, n]
void merge(int node, int l, int r, int m, int n, int value) {
    if (l > n || r < m) return; // 如果区间不重叠，直接返回
    if (l >= m && r <= n) { // 区间完全包含于[l, r]
        tree[node] = value;
        return;
    }
    int mid = (l + r) / 2;
    merge(node * 2, l, mid, m, min(n, mid), value); // 更新左子树
    merge(node * 2 + 1, mid + 1, r, max(m, mid + 1), n, value); // 更新右子树
    tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 合并子树
}

// 使用示例
void update(int node, int l, int r, int pos, int val) {
    merge(node, l, r, pos, pos, val);
}

// 查询区间[l, r]的和
int query(int node, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tree[node];
    int mid = (l + r) / 2, sum = 0;
    if (L <= mid) sum += query(node * 2, l, mid, L, R);
    if (R > mid) sum += query(node * 2 + 1, mid + 1, r, L, R);
    return sum;
}

int main() {
    // 初始化或填充线段树后，再使用update和query方法进行操作
    // 例如：
    // update(1, 0, N - 1, 3, 5); // 将索引为3的元素值更新为5
    // int sum = query(1, 0, N - 1, 1, 4); // 计算区间[1, 4]的和

    return 0;
}