目录

线段树学习笔记

03-15-2021 约 233 字预计阅读 1 分钟

目录

前置知识

位运算
字节点的编号

左子节点id=id«2,右子节点id=id«2|1（+1）

节点中存的是区间，不是具体数

建树

函数的参数:id(当前节点的编号),l,r(它所管辖的区间边界) 外置参数:a[id]存储原始数据 code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void build(int id, int l, int r)
{
    t[id].l = l;//设定边界
    t[id].r = r;
    if (l == r)//叶子节点
    {
        t[id].sum = a[id];
        return;
    }
    int mid = (l + r) / 2;//中点
    build(lid, l, mid);//递归建左区间
    build(rid, mid + 1, r);
    t[id].sum = t[lid].sum + t[rid].sum;//父节点的值为子节点的和
}