博客

学习线段树数月，一直处于懵懂状态，直到找到一个线段树模板

https://leetcode.cn/problems/my-calendar-iii/solution/pythonjavatypescriptgo-by-himymben-jb1u/

本例子是用线段树来求区间的最大值

• query将区间+val,并返回区间的最大值

class Node {
public:
    Node* ls, * rs;
    int val, add;
    Node():add(0),val(0),ls(nullptr),rs(nullptr) {
    }
};
class SegmentTree {
public:
    Node* root;
    SegmentTree() {
        root = new Node();
    }

	//lc,rc节点区间，l,r所求区间
    void update(Node* node, int lc, int rc, int l, int r, int v) {
    //如果节点区间比所求区间小，直接更新，其中add是lazy标记，表示区间内的所有节点+v
        if (l <= lc && rc <= r) {
            node->val += v;
            node->add += v;
            return;
        }
     //将节点下沉
        pushdown(node);
        
        int mid = (lc + rc) >> 1;
   	//如果左子节点的区间与要求的节点有交集，更新左子节点
        if (l <= mid) {
            update(node->ls, lc, mid, l, r, v);
        }
   //如果右子节点与更新的区间有交集，更新右子节点
        if (r > mid) {
            update(node->rs, mid + 1, rc, l, r, v);
        }
  //将节点的值，上传的根节点
        pushup(node);
    }

    int query(Node* node, int lc, int rc, int l, int r) {
    //当查询的区间与节点的区间相同，就直接返回
            if (l <= lc && rc <= r) {
            return node->val;
        }
    //否则如果有lazy标记就下沉标记
        pushdown(node);
        int ans = 0, mid = (lc + rc) >> 1;
        //查询左节点
        if (l <= mid) {
            ans = query(node->ls, lc, mid, l, r);
        }
       //查询右节点
        if (r > mid) {
            ans = max(ans, query(node->rs, mid + 1, rc, l, r));
        }
        return ans;
    }

    void pushdown(Node* node) {
    //在下沉的过程中，如果左右节点不存在，就创建新节点，
        if (node->ls == nullptr) {
            node->ls = new Node();
        }
        if (node->rs == nullptr) {
            node->rs = new Node();
        }
   //如果Lazy节点没有被标记，就直接返回
        if (node->add == 0) {
            return;
        }
   //否则要更新节点值，以及左右子节点的lazy值，并将当前节点的lazy值清空
        node->ls->val += node->add;
        node->ls->add += node->add;
        node->rs->val += node->add;
        node->rs->add += node->add;
        node->add = 0;
    }

    void pushup(Node* node) {
   	//上传到根节点的意思就是另节点的val等于左右节点的最大值
        node->val = max(node->ls->val, node->rs->val);
    }


};

class MyCalendarThree {
public:
    SegmentTree* sg;
    MyCalendarThree() {
        sg = new SegmentTree();
    }

    int book(int start, int end) {
        sg->update(sg->root, 0, 1e9, start, end - 1, 1);
        return sg->query(sg->root, 0, 1e9, 0, 1e9);
    }
};