// nums是給定大小為n的數(shù)組，par表示當(dāng)前正在構(gòu)建的線段樹節(jié)點下標(biāo)，start和end是當(dāng)前需要計算的區(qū)間。
void build(vector<int>& nums, int par, int start, int end)
{
    if (start == end) // 區(qū)間大小為1，即單個點，因此當(dāng)前節(jié)點的區(qū)間和就是單點的值
    {
        _segmentTree[par] = nums[start];
        return;
    }
    // 如果區(qū)間大于1，則先求當(dāng)前節(jié)點的左孩子和右孩子
    int mid = start + (end - start >> 1);
    int lchild = 2 * par + 1;
    int rchild = 2 * par + 2;
    build(nums, lchild, start, mid);   // 遞歸求左節(jié)點的區(qū)間和
    build(nums, rchild, mid + 1, end); // 遞歸求右孩子的區(qū)間和
    // 當(dāng)前節(jié)點的值就是左孩子的值+右孩子的值
    _segmentTree[par] = _segmentTree[lchild] + _segmentTree[rchild];
}

void update(int index, int val, int par, int start, int end)
{
    if (start == end) // 遞歸結(jié)束條件依然是當(dāng)前區(qū)間為單點
    {
        segtree[par] = val;
        return;
    }
    int mid = start + (end - start >> 1);
    // 遞歸修改左孩子或右孩子
    if (index <= mid)
        update(index, val, 2 * par + 1, start, mid);
    else
        update(index, val, 2 * par + 2, mid + 1, end);
    // 修改完成后重新對父節(jié)點賦值
    pushUp(par);
}
// pushUp負責(zé)利用左右孩子的值更新父節(jié)點
void pushUp(int par)
{
    segtree[par] = segtree[2 * par + 1] + segtree[2 * par + 2];
}

// [left, right]是目標(biāo)求和區(qū)間，par是當(dāng)前節(jié)點編號，當(dāng)前節(jié)點存儲區(qū)間[start, end]的和
int query(int left, int right, int par, int start, int end)
{
    // 目標(biāo)求和區(qū)間與當(dāng)前節(jié)點的區(qū)間吻合，直接返回當(dāng)前節(jié)點的值即可
    if (left == start && right == end)
        return segtree[par];
    int mid = start + (end - start >> 1);
    if (right <= mid) // 目標(biāo)求和區(qū)間全部在左子樹
        return query(left, right, 2 * par + 1, start, mid);
    else if (left > mid) // 目標(biāo)求和區(qū)間全部在右子樹
        return query(left, right, 2 * par + 2, mid + 1, end);
    else  // 目標(biāo)求和區(qū)間分布在左右子樹上
        return query(left, mid, 2 * par + 1, start, mid) +
               query(mid + 1, right, 2 * par + 2, mid + 1, end);
}

// 以「將給定區(qū)間內(nèi)的數(shù)加x，查詢每個節(jié)點存儲對應(yīng)區(qū)間的和」為例：
void update(int left, int right, int x, int node, int start, int end)
{
    // 區(qū)間沒有交集，無需修改
    if (end < left || right < start)
        return;
    // 當(dāng)前節(jié)點對應(yīng)的區(qū)間被需要修改的區(qū)間完全包含
    if (left <= start && right >= end)
    {
        segtree[node].val += x * (end - start + 1);
        segtree[node].lazy += x;
        return;
    }
    // 不被[left, right]完全包含，則說明本輪只會更新[start, end]的一部分，因此不能再"偷懶"直接將x加在lazy上了
    // 而是先根據(jù)lazy的值修改左右子節(jié)點，然后再遞歸修改左右子樹
    int mid = start + ((end - start) >> 1);
    // 先利用lazy修改孩子節(jié)點
    pushDown(node, mid - start + 1, end - mid);
    // 遞歸修改孩子節(jié)點
    update(left, right, 2 * node + 1, start, mid);
    update(left, right, 2 * node + 2, mid + 1, end);
    // 利用左右子樹的區(qū)間最大值確定父節(jié)點的區(qū)間最大值
    pushUp(par);
}
void pushUp(int par)
{
	segtree[par].val = segtree[2 * par + 1] + segtree[2 * par + 2] + segtree[par].lazy;
}
// par表示父節(jié)點，ln表示左孩子的區(qū)間長度，rn表示右孩子的區(qū)間長度
void pushDown(int par, int ln, int rn)
{
    if (segtree[par].lazy != 0)
    {
        segtree[2 * par + 1].val += segtree[par].lazy * ln; // 修改左孩子的值
        segtree[2 * par + 1].lazy += segtree[par].lazy; // 偷懶，不再往下繼續(xù)修改，因此左孩子繼承父節(jié)點的lazy值
        segtree[2 * par + 2].lazy += segtree[par].lazy * rn;
        segtree[2 * par + 2].lazy += segtree[par].lazy;
        segtree[par].lazy = 0; // 父節(jié)點的lazy已經(jīng)分配到子節(jié)點了，因此父節(jié)點lazy清零
    }
}

// 以「將給定區(qū)間內(nèi)的數(shù)加x，查詢每個節(jié)點存儲對應(yīng)區(qū)間的和」為例：
bool query(int left, int right, int node, int start, int end)
{
    // 區(qū)間沒有交集，無需查詢
    if (end < left || right < start)
        return false;
    // 有懶標(biāo)記，則無需查詢左右孩子，而是直接返回節(jié)點值，外加懶標(biāo)記
    // 或者當(dāng)前節(jié)點對應(yīng)的區(qū)間被需要查詢的區(qū)間完全包含，則直接返回節(jié)點值
    if (segtree[node].lazy || left <= start && right >= end)
        return segtree[node].val;
    int mid = start + ((end - start) >> 1);
    // 不完全包含，則先根據(jù)lazy修改子節(jié)點，再遞歸查詢左右子樹的和
    pushDown(node, mid - start + 1, end - mid);  
    return query(left, right, 2 * node + 1, start, mid) +
           query(left, right, 2 * node + 2, mid + 1, end);
}
// par表示父節(jié)點，ln表示左孩子的區(qū)間長度，rn表示右孩子的區(qū)間長度
void pushDown(int par, int ln, int rn)
{
    if (segtree[par].lazy != 0)
    {
        segtree[2 * par + 1].val += segtree[par].lazy * ln; // 修改左孩子的值
        segtree[2 * par + 1].lazy += segtree[par].lazy; // 偷懶，不再往下繼續(xù)修改，因此左孩子繼承父節(jié)點的lazy值
        segtree[2 * par + 2].lazy += segtree[par].lazy * rn;
        segtree[2 * par + 2].lazy += segtree[par].lazy;
        segtree[par].lazy = 0; // 父節(jié)點的lazy已經(jīng)分配到子節(jié)點了，因此父節(jié)點lazy清零
    }
}