5-5-线段数.md

线段数模版

c++

例题：729. 我的日程安排表 I

线段树模版题「汇总级别整理 🔥🔥🔥」

线段树从入门到急停：https://leetcode.cn/circle/discuss/H4aMOn/

struct Node{
    int l, r;
    int sum;
};

class NumArray {
private:
    vector<Node> tr;
    vector<int> nums;
    int n;
public:
    NumArray(vector<int>& nums) 
    {
        n = nums.size();
        tr = vector<Node>(n * 4);
        this -> nums = nums;
        build(1, 1, n);//建立线段树
    }
    
    void update(int index, int val) 
    {
        modify(1, index + 1, val);
    }
    
    int sumRange(int left, int right) 
    {
        return query(1, left + 1, right + 1).sum;
    }

    void build(int u, int l, int r)
    {
        if (l == r) tr[u] = {l, r, nums[l - 1]};
        else
        {
            tr[u] = {l, r};
            int mid = l + r >> 1;
            build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }//线段树初始化

    void pushup(Node &u, Node &l, Node &r)
    {
        u.sum = l.sum + r.sum;
    }//向上调整

    void pushup(int u)
    {
        pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
    }//向上调整

    void modify(int u, int x, int val)
    {
        if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, val};
        else
        {
            int mid = tr[u].l + tr[u].r >> 1;
            if (x <= mid) modify(u << 1, x, val);//左边更新
            else modify(u << 1 | 1, x, val);//右边更新
            pushup(u);//向上更新父节点
        }
    }

    Node query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u];//返回结点
        else
        {
            int mid = tr[u].l + tr[u].r >> 1;
            if (r <= mid) return query(u << 1, l, r);//左边查询
            else if (l > mid) return query(u << 1 | 1, l, r);//右边查询
            else
            {
                auto left = query(u << 1, l, r);
                auto right = query(u << 1 | 1, l, r);
                Node res;
                pushup(res, left, right);//两边查询后返回结点和
                return res;
            }
        }
    }

};