算法学习：线段树

核心思想

线段树（Segment Tree）是一种平衡树型数据结构，主要用于区间查询和区间更新问题。

适用场景：求数组某个区间的和、最大值、最小值。
动态更新数组元素，同时仍能快速查询区间信息。

特点：
查询和更新的时间复杂度为 O(log n)。
空间复杂度为 O(4n)（常用数组实现，也可以用树形结构存储）。

---

求和（动态开点，单点更新）

template<class T>
class SumSegTree {
    struct Node {
        size_t L, R,MID;
        T val;
        Node *left,*right;
        T sum(size_t l, size_t r) {
            if(l>r) return 0;
            if(r < this->L || l > this->R) return 0;
            if(l <= this->L && r >= this->R) return this->val;
            T leftvalue=0, rightvalue=0;
            if(l<=this->MID && this->left) {
                leftvalue = this->left->sum(l, r);
            }
            if(r>this->MID && this->right) {
                rightvalue = this->right->sum(l, r);
            }
            return leftvalue+rightvalue;
        }
        void update(size_t x, T val) {
            if(this->R < x || this->L > x) return;
            if(L==R) {
                //cout << "[update] set leaf " << L << " " << x << endl;
                this->val = val;
                return;
            }
            if(!this->left) addNode(this->left, this->L, this->MID);
            if(!this->right) addNode(this->right, this->MID+1, this->R);
            if(x<=this->MID) {
                this->left->update(x, val);
            }
            if(x>this->MID) {
                this->right->update(x, val);
            }
            this->val = this->left->val + this->right->val; // 此外，这里要注意我们维持的是树本身的性质（即使x只涉及左孩子或右孩子，我们也要记得加上另一个节点才能维持树的性质）
        }
        void addNode(Node*&node, size_t tl, size_t tr) {
            node = new Node();
            node->L = tl;
            node->R = tr;
            node->val = 0;
            node->MID = tl+(tr-tl)/2;
            node->left=node->right=nullptr;
        }
    };
    Node root;
public:
    SumSegTree(size_t MAXN) {
        root.L = 1;
        root.R = MAXN;
        root.MID = 1+(MAXN-1)/2;
        root.left=root.right=nullptr;
        root.val = 0;
    }
    void update(size_t x, T val) {
        root.update(x, val);
    }
    T sum(size_t l, size_t r) {
        return root.sum(l, r);
    }
};

例题：LEETCODE307：https://leetcode.cn/problems/falling-squares/

class NumArray {
    SumSegTree<int> t;
public:
    NumArray(vector<int>& nums)
    : t(nums.size())
    {
        for(int i=0; i<nums.size(); i++) {
            t.update(i+1, nums[i]);
        }
    }
    
    void update(int index, int val) {
        t.update(index+1, val);
    }
    
    int sumRange(int left, int right) {
        return t.sum(left+1, right+1);
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 */

---

最大值（动态开点，懒标记区间修改）

template<class T>
class MaxValueSegTree {
private:
    static const T MIN = 0;
    struct Node {
        size_t L, R, MID;
        T val;
        T lazy;
        Node *left, *right;
        T maxValue(size_t l, size_t r) {
            if (l > r) return MIN;
            if (this->L >= l && this->R <= r) {
                // 对于所查询区间，整颗树的信息已经在当前节点包含，无需再递归
                return this->val;
            }
            if (r < this->L || l > this->R) {
                return MIN;
            }
            pushdown(); // 不要忘记查询和修改在向下递归前都要pushdown
            T leftValue = MIN, rightValue = MIN;
            if (l <= this->MID && this->left) {
                leftValue = this->left->maxValue(l, r);
            }
            if (r > this->MID && this->right) {
                rightValue = this->right->maxValue(l, r);
            }
            return max(leftValue, rightValue); // 如要更改为求和等，则这里从子节点汇总也要对应修改
        }
        void setMax(size_t l, size_t r, T val) {
            if (l > r) return;
            if (r < this->L || l > this->R) return;
            if (l <= this->L && r >=this->R) {
                this->val = val;
                this->lazy = val;
                return;
            }
            pushdown(); // 不要忘记查询和修改在向下递归前都要pushdown
            if (l <= this->MID) {
                this->left->setMax(l, r, val);
            }
            if (r > this->MID) {
                this->right->setMax(l, r, val);
            }
            // 如要更改为求和等，则这里从子节点汇总也要对应修改
            this->val = max(this->val, this->left->val); // 此外，这里要注意我们维持的是树本身的性质（即使子节点所代表的某些点不在修改范围中，我们也要把左右子节点所代表的所有数据都汇总上来，我们）
            this->val = max(this->val, this->right->val);
        }
        void addNewNode(Node *&node, int newTL, int newTR) {
            node = new Node();
            node->L = newTL;
            node->R = newTR;
            node->MID = newTL + (newTR-newTL)/2;
            node->val = MIN;
            node->lazy = MIN;
            node->left = node->right = nullptr;
        }
        void pushdown() {
            if(!this->left) addNewNode(this->left, this->L, this->MID);
            if(!this->right) addNewNode(this->right, this->MID+1, this->R);
            if (this->lazy != MIN) {
                Node* left = this->left;
                Node* right = this->right;

                // 如要更改为求和等，则这里从子节点汇总也要对应修改，如
                // left->val += this->lazy;
                // right->val += this->lazy;
                // left->lazy += this->lazy;
                // right->lazy += this->lazy;

                left->val = max(left->val, this->lazy);
                right->val = max(right->val, this->lazy);
                left->lazy = max(left->lazy, this->lazy);
                right->lazy = max(right->lazy, this->lazy);
                this->lazy = MIN;
            }
        }
    };
    Node root;
public:
    MaxValueSegTree(size_t MAXN) {
        root.L = 1;
        root.R = MAXN;
        root.MID = 1 + (MAXN-1)/2;
        root.val = MIN;
        root.lazy = MIN;
        root.left = root.right = nullptr;
    }
    void setMax(size_t l, size_t r, T val) {
        root.setMax(l, r, val);
    }
    T maxValue(size_t l, size_t r) {
        return root.maxValue(l, r);
    }

};

例题：LEETCODE699：https://leetcode.cn/problems/falling-squares/

class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        vector<int> ans;
        ans.reserve(positions.size());
        int maxh = 0;
        MaxValueSegTree<int> t(100000000);
        for (vector<int>& range: positions) {

            size_t l = range[0], r = range[0] + range[1]-1;
            int h = t.maxValue(l, r);
            t.setMax(l, r, h+range[1]);
            maxh = max(maxh, h+range[1]);
            ans.push_back(maxh);
        }
        return ans;
    }
};

Donate