[데이터 구조] [선분 트 리] 단점 수정 구간 조회

#include 
#include 
#include 
#include 
using namespace std;

const int MAXSIZE = 50005;

int T,n,x,y,a[MAXSIZE],sum[MAXSIZE*4];
char ask[10];

inline void update(int root)					//       
{
	sum[root]=sum[root<<1]+sum[root<<1|1];
}

void build(int now_root, int l, int r)			//      
{
	if (l==r)
	{
		sum[now_root]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(now_root<<1,l,mid);
	build(now_root<<1|1,mid+1,r);
	update(now_root);
}

void modify(int i, int l, int r, int x, int d)	//  : x  d 
{
	if (l==r)
	{
		sum[i]+=d;
		return;
	}
	int mid=(l+r)>>1;
	if (x<=mid) modify(i<<1,l,mid,x,d);
	else modify(i<<1|1,mid+1,r,x,d);
	update(i);
}

int query(int i, int l, int r, int L, int R)	//  L R    
{
	if (L<=l&&r<=R)
		return sum[i];
	int mid=(l+r)>>1;
	int ans=0;
	if (L<=mid) ans+=query(i<<1,l,mid,L,R);
	if (mid

HDU 1166 수 정 된 템 플 릿 입 니 다. 선분 트 리 로 구간 을 유지 하고 단점 수정 과 구간 조회 작업 을 지원 합 니 다.

좋은 웹페이지 즐겨찾기