선분 트 리 고전 작업 템 플 릿 (단일 업데이트, 교체, 구간 업데이트, 교체, 구간 구 와 최 값 구 함)

선분 트 리 에 대한 설명 은 더 이상 군말 하지 않 습 니 다. 다음은 선분 트 리 응용 에서 가장 자주 사용 하 는 몇 가지 조작 코드 를 보 여 줍 니 다.(구체 적 인 제목 은 붙 이지 않 았 고 일정한 기초 자 만 코드 스타일 을 참고 할 수 있 습 니 다)
또한, scanf ("% d% d", & n, & m) 를 쓰 려 면 여러 그룹의 입력 을 주의 하 십시오! =EOF, 선분 트 리 의 문 제 는 반드시 c 언어의 입 출력 을 사용 해 야 합 니 다. 문자 배열 을 사용 해 야 합 니 다. 문자열 을 사용 하지 않 고 문 자 를 입력 할 때 getchar () 를 추가 하여 빈 줄 을 삼 켜 야 합 니 다.
(1) 단점 증감, 구간 구 화:

#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
using namespace std;
int a[50000*4];//      
int sum[50000*4];
int T,n,b,c,ans;
char s[20];
//    ，    
int build(int l,int r,int o)//l ，r ,o   
{
	if(l==r)//       
	return sum[ o]=a[l];
	else
	{
		int mid=l+(r-l)/2;
		return sum[o]=build(l,mid,2*o)+build(mid+1,r,2*o+1); 
	}
	
}
void query(int l,int r,int o)//b，c        
{
	if(b<=l&&c>=r)//   b，c  l，r 
	ans+=sum[o];
	else
	{
		int mid=l+(r-l)/2;
		if(b<=mid)
		query(l,mid,o*2);
	    if(c>mid)
		query(mid+1,r,2*o+1);
	} 
}
void add(int l,int r,int o)
{
	sum[o]+=c;//          
	if(l==r)
	return;
	else
	{
	  int mid=l+(r-l)/2;
	  if(b<=mid)
	  add(l,mid,o*2);
	  else
	  add(mid+1,r,o*2+1);	
	}
}
int main()
{
	int ca=1;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		printf("Case %d:
",ca++);
		build(1,n,1);
		while(scanf("%s",s))
		{
			if(s[0]=='E')
			break;
			if(s[0]=='A')
			{
				scanf("%d%d",&b,&c);
				add(1,n,1);
			}
			if(s[0]=='S')
			{
			   scanf("%d%d",&b,&c);
				c=-c;
				add(1,n,1);
			}
		
			if(s[0]=='Q')
			{
				ans=0;
				scanf("%d%d",&b,&c);
				query(1,n,1);
			    printf("%d
",ans);
			}
		}
	}
	return 0;

(2) 단일 업데이트, 구간 최대 값 구하 기

int build(int l,int r,int o)//l ，r ,o   
{
	if(l==r)//       
	return max1[o]=a[l];//     
	else
	{
		int mid=l+(r-l)/2;
		return max1[o]=max(build(l,mid,2*o),build(mid+1,r,2*o+1)); 
	}
	
}
void update(int l,int r,int o)//     
{
//	sum[o]+=c;
    max1[o]=max(max1[o],c);//               
	if(l==r)
	return;
	else
	{
	  int mid=l+(r-l)/2;
	  if(b<=mid)
	  update(l,mid,o*2);
	  else
	  update(mid+1,r,o*2+1);	
	}
}

void query(int l,int r,int o)//b，c         
{
	if(b<=l&&c>=r)//   b，c  l，r 
	ans=max(ans,max1[o]);//    ，ans   0 
		//ans+=sum[o];
	else
	{
		int mid=l+(r-l)/2;
		if(b<=mid)
		query(l,mid,o*2);
	    if(c>mid)
		query(mid+1,r,2*o+1);
	} 
}	

(3) 구간 교체, 구간 구 화

#include<iostream>
#include<stdio.h>
using namespace std;
const int MAX_N=100100;
int sum[MAX_N<<2],col[MAX_N<<2];
int n,q,x,y,c;

void push_down(int l,int r,int o)//   
{
	int m=(l+r)>>1;
	if(col[o])
	{
		col[o<<1]=col[o<<1|1]=col[o];
		sum[o<<1]=(m-l+1)*col[o];
		sum[o<<1|1]=(r-m)*col[o];
		col[o]=0;
	}
}
void build(int l,int r,int o)
{
	col[o]=0;
	sum[o]=1;
	if(l==r)
	return ;
	int m=(l+r)>>1;
	build(l,m,o<<1);
	build(m+1,r,o<<1|1);
	sum[o]=sum[o<<1]+sum[o<<1|1];
}

void update(int l,int r,int o)
{
	int m=(l+r)>>1;
	if(x<=l&&r<=y)
	{
		col[o]=c;
		sum[o]=(r-l+1)*c;
		return ;
	}
	push_down(l,r,o);
	if(x<=m)
	update(l,m,o<<1);
	if(y>m)
	update(m+1,r,o<<1|1);
	sum[o]=sum[o<<1]+sum[o<<1|1];
}
int main()
{
	int T,cas=1;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&q);
		build(1,n,1);
		while(q--)
		{
		   scanf("%d%d%d", &x, &y, &c);
		   update(1,n,1);
		}
		printf("Case %d: The total value of the hook is %d.
", cas++, sum[1]);
	}
	return 0;
}

(4) 구간 업데이트, 구간 구 화

#include <iostream>
#include <cstdio>
using namespace std;
#define N 100005
__int64 sum[N << 2];
__int64 mark[N << 2];
__int64 basic_num[N<<2];
inline void pushUp (int o)
{
    sum[o] = sum[o << 1] + sum[o << 1 | 1];
}

void pushDown (int o, int len)
{
    if (mark[o]) {
        //  o              ，  o             o       ，   “+=”
        mark[o << 1] += mark[o];
        mark[o << 1 | 1] += mark[o];
        /*   mark[o]      ，  mark[o<<1],   o            ，      ，
              sum[o<<1]    。
        */
        sum[o << 1] += mark[o] * (len - (len >> 1)); 
        sum[o << 1 | 1] += mark[o] * (len >> 1);
        mark[o] = 0; //           ，          
    }
}

void build (int l, int r, int o)
{
    mark[o] = 0;
    if (l == r)
    {
        sum[o]=basic_num[l];
        return;
    }
    int m = (l + r) >> 1;
    build (l, m, o << 1);
    build (m + 1, r, o << 1 | 1);
    pushUp (o);//sum     
}

void update (int L, int R, __int64 c, int l, int r, int o)//L，R        
{
    if (l >= L && r <= R)
    {
        mark[o] += c;
        sum[o] += c * (r - l + 1);
        return;
    }
    /*                        ，              
      ，                ，               ，    
                O（logn），           。
    */
    pushDown(o, r - l + 1); //            
    int m = (l + r) >> 1;
    if (m >= L) update (L, R, c, l, m, o << 1);
    if (m < R) update (L, R, c, m + 1, r, o << 1 | 1);
    pushUp (o);
}

__int64 query (int L, int R, int l, int r, int o)
{
    if (l >= L && r <= R) 
	return sum[o];
    //  o      ，    o         
    pushDown(o, r - l + 1);
    int m = (l + r) >> 1;
    __int64 ret = 0;
    if (m >= L) ret += query (L, R, l, m, o << 1);
    if (m < R) ret += query (L, R, m + 1, r, o << 1 | 1);
    return ret;
}

int main()
{
    int n, q, a, b;
    __int64 c;
    char op;
    scanf ("%d%d", &n,&q);
    for(int i=1;i<=n;i++)
    scanf("%I64d",&basic_num[i]);
    build (1, n, 1);
    while (q--)
    {
        getchar();
        scanf ("%c %d %d", &op, &a, &b);
        if (op == 'Q') printf ("%I64d
", query (a, b, 1, n, 1));
        else
        {
            scanf ("%I64d", &c);
            update (a, b, c, 1, n, 1);
        }
    }
    return 0;
}