セグメントツリーの一般的なルート

線分樹は二叉樹で、
二叉木に区間を設ける.
だから最初の板はどのように木を建てるのか、私は直接建てるのが好きで、暴力的です.
マクロ定義は遅いですが、便利です.

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

PS:マクロは実際にテキストを呼び出すので、マクロ定義のアルファベット変数はその時に関数の呼び出しアルファベットと一致しなければならない.そうしないと、エラーが発生する

<strong>void Build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%d",&MAX[rt]);
        return;
    }
    int m=(l+r)>>1;
    Build(lson);
    Build(rson);
}</strong>

単一ノードの更新:座標の値を値に変更します.

<strong>void Update(int p,int add,int l,int r,int rt)
{
    if(l==r)
    {
        MAX[rt]=add;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)
        Update(p,add,lson);
    else
        Update(p,add,rson);
    
    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
</strong>

最大値クエリー

<strong>void Build(int l,int r,int rt)//* 
{
    if(l==r)
    {
        scanf("%d",&MAX[rt]);
        return;
    }
    int m=(l+r)>>1;
    Build(lson);
    Build(rson);
    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}

int Query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)
        return MAX[rt];
    int m=(l+r)>>1;
    int ret=0;
    if(L<=m)   ret=max(ret,Query(L,R,lson));
    if(R>m)    ret=max(ret,Query(L,R,rson));
    return ret;
}</strong>

最小値クエリー

<strong>void Build(int l,int r,int rt)//*  
{
    if(l==r)
    {
        scanf("%d",&MAX[rt]);
        return;
    }
    int m=(l+r)>>1;
    Build(lson);
    Build(rson);
    MAX[rt]=min(MAX[rt<<1],MAX[rt<<1|1]);
}
int Query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)
        return MAX[rt];
    int m=(l+r)>>1;
    int ret=0;
    if(L<=m)   ret=min(ret,Query(L,R,lson));
    if(R>m)    ret=min(ret,Query(L,R,rson));
    return ret;
}
</strong>

クエリー区間と
区間和を更新するには、現在の値を格納する必要があります.その中で、ブラックテクノロジーinline関数を使用することができます.

#include <bits/stdc++.h> 
using namespace std ;
#define N 500005 
#define lson l,m,rt<<1  
#define rson m+1,r,rt<<1|1  

int sum[N<<2];

inline void PushPlus(int rt)
{
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void build(int l, int r, int rt)  
{  
    if(l == r)  
   {  
        scanf("%d", &sum[rt]);  
        return ;  
   }  
    int m = ( l + r )>>1;  
  
   build(lson);  
    build(rson);  
   PushPlus(rt);  
}  
int search(int L ,int R ,int l , int r , int rt)
{
	int ans = 0 ;	
	if(L<=l&&R>=r)
	{
		return sum[rt];
	}
	int m = (l+r)>>1;
	if(L<=m) ans += search(L,R,lson);
	if(R>m) ans += search(L,R,rson);
	return ans ;
}

ダイナミック更新区間点

#define lson l , m , rt << 1  
#define rson m + 1 , r , rt << 1 | 1 
#define root 1 , N , 1 
#define LL long long  
const int maxn = 111111;  
LL add[maxn<<2];  
LL sum[maxn<<2];  
void PushUp(int rt) {  
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];  
}  
void PushDown(int rt,int m) {  
    if (add[rt]) {  
        add[rt<<1] += add[rt];  
        add[rt<<1|1] += add[rt];  
        sum[rt<<1] += add[rt] * (m - (m >> 1));  
        sum[rt<<1|1] += add[rt] * (m >> 1);  
        add[rt] = 0;  
    }  
}  
void build(int l,int r,int rt) {  
    add[rt] = 0;  
    if (l == r) {  
        scanf("%lld",&sum[rt]);  
        return ;  
    }  
    int m = (l + r) >> 1;  
    build(lson);  
    build(rson);  
    PushUp(rt);  
}  
void update(int L,int R,int c,int l,int r,int rt) {  
    if (L <= l && r <= R) {  
        add[rt] += c;  
        sum[rt] += (LL)c * (r - l + 1);  
        return ;  
    }  
    PushDown(rt , r - l + 1);  
    int m = (l + r) >> 1;  
    if (L <= m) update(L , R , c , lson);  
    if (m < R) update(L , R , c , rson);  
    PushUp(rt);  
}