樹——區間查詢和修改問題————線段樹（模闆1.0）

普通區間修改和查詢 （帶懶惰标記）模闆

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+50;
struct node
{
    int l, r;//區間左右端點
    int sum;//區間資訊, 可以是最值、 區間和、等等
    int lazy;//懶惰标記 
}Segtr[maxn*4];// 開4倍空間， 這個是大佬們計算出的

void pushdown(int rt)// 懶惰标記下壓函數
{
    /********
        此處有更新操作， 按照題意
    ***********/
    //下壓标記
    Segtr[rt*2+1].lazy = Segtr[rt].lazy;
    Segtr[rt*2+2].lazy = Segtr[rt].lazy;
    Segetr[rt].lazy = 0;
}
void pushup(int rt)
{
    Segtr[rt].sum = Segtr[rt*2+1].sum+Segtr[rt*2+2].sum;//回溯更新操作， 按照題意
}
void build(int l, int r, int rt)// 分别表示區間的左右端點， 和區間對應結點的編号
{
    //初始化
    Segtr[rt].l = l;
    Segtr[rt].r = r;
    Segtr[rt].lazy = 0;
    Segtr[rt].sum = 0;
    if(l == r)return;//遞歸到葉子結點傳回
    int mid = (l+r)/2; //可以換成（l+r）>>1;
    build(l, mid, rt*2+1);//建立左子樹
    build(mid+1, r, rt*2+2);//建立右子樹
    pushup(rt);// 回溯維護父結點
}
void update(int L, int R, int rt, int v)//分别表示要更新區間額左右端點 和對應的結點編号， 和更新的值
{
    int l = Segtr[rt].l;
    int r = Segtr[rt].r;
    
    if(l == L&& r == R)// 找到要更細的直接區間，将其更新， 然後打上标記
    {
        Segtr[rt].sum += (R-L+1)*add;
        Segtr[rt].lazy +=add;
        return;
    }
    if(Segtr[rt].lazy) pushdown(rt); //如果有标記就下壓标記
    int mid = (l+r)/2;
    if(R <= mid) update(L, R, rt*2+1, add);
    else if(L > mid) update(L, R, rt*2+2, add);
    else 
    {
       update(L, mid, rt*2+1, add);
       update(mid+1, R, rt*2+2, add);
    }
    
    pushup(rt); //回溯維護父親
}
int query(int L, int R, int rt)// 查詢函數
{
    int res = 0;
    int l = Segtr[rt].l;
    int r = Segtr[rt].r;
    
    if(l == L && r == R)
    {
        return Segtr[rt].sum;
    }
    if(Segtr[rt].lazy)pushdown(rt);
    
    int mid = (l+r)/2;
    
    if(R <= mid)res+=query(L, R, rt*2+1);
    else if(L > mid)res+=query(L, R, rt*2+2);
    else
    {
        res+=query(L, mid, rt*2+1);
        res+=query(mid+1, R, rt*2+2);
    }
    return res;
}
int main()
{
    
    
    return 0;
}