用c++写线段树模板

### 回答1：
线段树是一种用于处理区间查询和修改的数据结构。下面是一份 C 语言实现的线段树的模板代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m,tree[N<<2];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void pushup(int x){tree[x]=tree[ls(x)]+tree[rs(x)];}
void build(int p,int l,int r)
{
    if(l==r)
    {
        tree[p]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    pushup(p);
}
void modify(int p,int l,int r,int pos,int k)
{
    if(l==r)
    {
        tree[p]=k;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) modify(ls(p),l,mid,pos,k);
    else modify(rs(p),mid+1,r,pos,k);
    pushup(p);
}
int query(int p,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return tree[p];
    int mid=(l+r)>>1,sum=0;
    if(x<=mid) sum+=query(ls(p),l,mid,x,y);
    if(y>mid) sum+=query(rs(p),mid+1,r,x,y);
    return sum;
}
int main()
{
    return 0;
}

代码中的 `build` 函数用于建树，`modify` 函数用于单点修改，`query` 函数用于区间查询。记得根据具体问题修改 pushup 函数的内容以及区间修改和查询的具体操作。

### 回答2：
线段树（Segment Tree）是一种经典的数据结构，常用于解决区间查询问题。下面是使用C语言编写的线段树模板：

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int left, right;
    int sum;
} tree[4 * MAX_N];  // 线段树的最大节点数, MAX_N为数组的最大长度

// 构建线段树
void build(int node, int left, int right, int arr[]) {
    if (left == right) {
        tree[node].left = tree[node].right = left;
        tree[node].sum = arr[left];
        return;
    }

    int mid = (left + right) / 2;
    build(2 * node, left, mid, arr);
    build(2 * node + 1, mid + 1, right, arr);

    tree[node].left = left;
    tree[node].right = right;
    tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;
}

// 区间求和
int query(int node, int left, int right) {
    if (left <= tree[node].left && right >= tree[node].right) {
        return tree[node].sum;
    }

    int mid = (tree[node].left + tree[node].right) / 2;
    int sum = 0;
    if (left <= mid) {
        sum += query(2 * node, left, right);
    }
    if (right > mid) {
        sum += query(2 * node + 1, left, right);
    }

    return sum;
}

// 更新节点
void update(int node, int index, int value) {
    if (tree[node].left == tree[node].right) {
        tree[node].sum = value;
        return;
    }

    int mid = (tree[node].left + tree[node].right) / 2;
    if (index <= mid) {
        update(2 * node, index, value);
    }
    else {
        update(2 * node + 1, index, value);
    }

    tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;
}

int main() {
    int n;  // 数组长度
    int arr[MAX_N];  // 原始数组

    // 初始化数组
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // 构建线段树
    build(1, 0, n - 1, arr);

    // 示例查询和更新操作，具体应根据实际需求进行调整
    int sum = query(1, 0, 3);
    printf("区间和：%d\n", sum);

    update(1, 2, 5);

    sum = query(1, 0, 3);
    printf("更新后的区间和：%d\n", sum);

    return 0;
}

这是一个简单的线段树模板，其中主要包含了构建线段树、区间求和以及更新节点等常用操作，可以根据具体需求进行修改和扩展。

### 回答3：
线段树（Segment Tree）是一种用于解决区间查询问题的数据结构。下面是用C语言实现线段树的模板：

#include <stdio.h>
#include <stdlib.h>

// 线段树结点的定义
typedef struct TreeNode {
    int left;               // 区间左边界
    int right;              // 区间右边界
    int sum;                // 区间内元素的和
    struct TreeNode* leftChild;     // 左孩子结点指针
    struct TreeNode* rightChild;    // 右孩子结点指针
} TreeNode;

// 创建线段树的辅助函数
TreeNode* buildSegmentTree(int arr[], int left, int right) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->left = left;
    node->right = right;
    if (left == right) {                // 叶子结点
        node->sum = arr[left];
    } else {
        int mid = (left + right) / 2;
        node->leftChild = buildSegmentTree(arr, left, mid);        // 递归构建左子树
        node->rightChild = buildSegmentTree(arr, mid+1, right);    // 递归构建右子树
        node->sum = node->leftChild->sum + node->rightChild->sum;  // 更新父节点的和
    }
    return node;
}

// 查询区间和的函数
int query(TreeNode* node, int queryLeft, int queryRight) {
    if (node->left == queryLeft && node->right == queryRight) {   // 当前结点区间和正好等于查询区间
        return node->sum;
    } else {
        int mid = (node->left + node->right) / 2;
        if (queryRight <= mid) {            // 查询区间完全在左子树
            return query(node->leftChild, queryLeft, queryRight);
        } else if (queryLeft > mid) {       // 查询区间完全在右子树
            return query(node->rightChild, queryLeft, queryRight);
        } else {                           // 查询区间跨越左右子树
            int leftSum = query(node->leftChild, queryLeft, mid);
            int rightSum = query(node->rightChild, mid+1, queryRight);
            return leftSum + rightSum;
        }
    }
}

// 更新元素值的函数
void update(TreeNode* node, int index, int value) {
    if (node->left == node->right) {    // 找到对应的叶子结点
        node->sum = value;
    } else {
        int mid = (node->left + node->right) / 2;
        if (index <= mid) {              // 更新的元素在左子树
            update(node->leftChild, index, value);
        } else {                         // 更新的元素在右子树
            update(node->rightChild, index, value);
        }
        node->sum = node->leftChild->sum + node->rightChild->sum;  // 更新父节点的和
    }
}

// 测试线段树
int main() {
    int arr[] = {1, 3, 5, 7, 9, 11};  // 原始数组
    int n = sizeof(arr) / sizeof(arr[0]);

    TreeNode* root = buildSegmentTree(arr, 0, n-1);  // 构建线段树

    int sum = query(root, 1, 4);                    // 查询区间[1,4]的和
    printf("The sum of range [1,4] is: %d\n", sum);

    update(root, 2, 6);                             // 更新元素arr[2]为6

    sum = query(root, 1, 4);                         // 再次查询区间[1,4]的和
    printf("The sum of range [1,4] after update is: %d\n", sum);

    return 0;
}

以上是一个基本的线段树模板，实现了线段树的构建（buildSegmentTree）、区间查询（query）和元素更新（update）等功能。可以根据具体的问题需求，对模板进行相应的修改和扩展。