要素：

线段树的定义一般用结构体定义

struct Node{
    int l,r; // 左右儿子
    int // 需要维护的量
}tr[N*4];

基本操作：

1.build(u , l , r)

建立一棵线段树

通用代码：

void build(int u,int l,int r)
{
    tr[u]={···};// 加入点元素
    if(l == r) return;
    
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

2.pushup(u)

通过左右子节点信息计算父节点信息

通用代码：

void pushup(int u)
{
    tr[u].v=function(tr[u<<1].v,tr[u<<1|1].v);
    // v代表某种性质
}

3.pushdown(u)

：用父节点信息计算左右子节点的信息

懒标记：即为在修改时的修改值，用于对区间进行修改，使其用的时间复杂度进行区间修改，防止时间复杂度退化为

懒标记下传用

通用代码：

void pushdown(int u)
{
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(ro.flag)
    {
    	// 将懒标记下传至左右子节点
        left.flag->root.flag;
        right.flag->root.flag;
        // 对所维护的信息进行修改
        { · · · · · · }
        // 将根节点的懒标记去除
        root.flag=0;
    }
}
// flag表示懒标记

4.query(u , l , r)

对区间进行查询操作(求和、求最大值等)

通用代码：

int query(int u, int l, int r)
{
    if (tr[u].l>=l&&tr[u].r<=r) return tr[u].v;

    pushdown(u);
    
    int mid=tr[u].l+tr[u].r>>1;
    // 依题意选用以下两种操作方式
    if(求和)
    {
        int sum=0;
        if(l<=mid) sum=query(u<<1,l,r);
        if(r>mid) sum+=query(u<<1|1,l,r);
        return sum;
    }
    
    if(求值）
    {
        if(l<=mid) return query(u<<1,l,r);
        if(r>mid) return query(u<<1|1,l,r);
    }
}
// v表示维护的值

5.modify

该操作包含两种操作：

1>单点修改modify(u , x , v)：

：对单点进行修改(加/减一个数、改为一个数)

通用代码：

void modify(int u,int x,int v)
{
    if(tr[u].l==x&&tr[u].r==x) tr[u]={···};// 改为所需元素

    else 
    {
        int mid=tr[u].l+tr[u].r>>1;

        if(x>mid) modify(u<<1|1,x,v);
        else modify(u<<1,x,v);

        pushup(u);
    }
}

2>区间修改modify(u , l , r , v)：

:对区间进行修改(都加/减一个数、都改为一个数)

通用代码：

void modify(int u,int l,int r,int d)
{
    if(tr[u].l>=l&&tr[u].r<=r) 
    {
        // 加入懒标记
    }
    else 
    {
        pushdown(u);
        
        int mid=tr[u].l+tr[u].r>>1;
        if(l <= mid) modify(u<<1,l,r,d);
        if(mid<r) modify(u<<1|1,l,r,d);
        
        pushup(u);
    }
}