线段树
2026-06-13 14:34:25
发布于：浙江
12阅读
0回复
0点赞
线段树的构建:
#define int long long
void build(int p, int l, int r){ // 根节点 左节点 右节点
// 将左端点和右端点的数据放入p节点下
tree[p].l = l
tree[p].r = r;
if (l == r){ // 如果是叶子节点 (当左节点=右节点时，是最后一层)
tree[p].value = arr[l]; // 放入值，放入arr[r]也是一个道路
return;
}
int mid = (l + r) / 2;
build(p * 2, l, mid); // 构建左子树
build(p * 2 + 1, mid + 1, r); // 构建右子树
tree[p].value = tree[p * 2].value + tree[p * 2 + 1].value; // 回溯
}
单点修改:
void update(int p, int x, int z){ // 根节点 需要修改的节点 需要修改的值
if (tree[p].l == tree[p].r){// 对于找到的位置进行修改(给x的位置增加)
tree[p].value += z;
return;
}
int mid = (tree[p].l + tree[p].r) / 2; // 二分范围:当前节点左右 去划分
if (x <= m) update(p * 2, x, z); // 如果需要修改的右半边范围正好包含
else if(x > mid) update(p * 2 + 1, x, z);
tree[p].value = tree[p * 2].value + tree[p * 2 + 1].value; // 回溯
}
区间查询:
int query(int p, int x, int y){ // 根节点 查询区间左 查询区间右
if (x <= tree[p].l && y >= tree[p].r){
// 范围p下标包含的值
return tree[p].value;
}
int mid = (tree[p].l + tree[p].r) / 2; // 二分范围
int flag = 0; //记录总和
if (x <= mid) //如果需要修改的范围真好包含
flag += query(p * 2, x, y); //去左子树取值
if (y > mid) //如果需要修改的范围正好包含
flag += query(p * 2 + 1, x, y) //去右子树取值
return flag;
}
全部评论 1
为什么
tree[p].value = tree[p * 2].value + tree[p * 2 + 1].value; // 回溯是回溯，不是更新吗2天前 来自 浙江
0
有帮助，赞一个