선분 트 리 템 플 릿 (구간 과 최대 값 최 하 값)
//===========================================
//segment tree
//final version
//by kevin_samuel(fenice)
#include
#include
#include
using namespace std;
#define MAXN 100
#define INF 0x3fffffff
int A[MAXN];
//int max;
//int min;
struct node
{
int left;
int right;
int max; //
int sum; //
int min; //
}Tree[MAXN<<2];
void maintain(int root) //
{
int LC = root<<1;
int RC = (root<<1)+1;
Tree[root].sum = Tree[LC].sum + Tree[RC].sum;
Tree[root].max = max(Tree[LC].max,Tree[RC].max);
Tree[root].min = min(Tree[LC].min,Tree[RC].min);
}
void Build(int root,int start,int end) //
{
Tree[root].left = start;
Tree[root].right = end;
if(start == end)
{
Tree[root].sum = A[start];
Tree[root].max = A[start];
Tree[root].min = A[start];
return;
}
int mid = (start + end)>>1;
Build(root<<1,start,mid);
Build((root<<1)+1,mid+1,end);
maintain(root);
}
void update(int root,int pos,int value) //
{
if(Tree[root].left == Tree[root].right && Tree[root].left == pos)
{
Tree[root].sum += value;
Tree[root].max += value;
Tree[root].min += value;
return;
}
int mid = (Tree[root].left + Tree[root].right)>>1;
if(pos <= mid)
update(root<<1,pos,value);
else
update((root<<1)+1,pos,value);
maintain(root);
}
int Query(int root,int start,int end) //
{
if(start == Tree[root].left && Tree[root].right == end)
{
return Tree[root].sum;
}
int mid = (Tree[root].left + Tree[root].right)>>1;
int ret = 0;
if(end <= mid)
ret += Query(root<<1,start,end);
else if(start >= mid+1)
ret += Query((root<<1)+1,start,end);
else
{
ret += Query(root<<1,start,mid);
ret += Query((root<<1)+1,mid+1,end);
}
return ret;
}
int RminQ(int root,int start,int end) //
{
if(start == Tree[root].left && Tree[root].right == end)
{
return Tree[root].min;
}
int mid = (Tree[root].left + Tree[root].right)>>1;
int ret = INF;
if(end <= mid)
ret = min(ret,RminQ(root<<1,start,end));
else if(start >= mid+1)
ret = min(ret,RminQ((root<<1)+1,start,end));
else
{
int a = RminQ(root<<1,start,mid);
int b = RminQ((root<<1)+1,mid+1,end);
ret = min(a,b);
}
return ret;
}
int RmaxQ(int root,int start,int end) //
{
if(start == Tree[root].left && Tree[root].right == end)
{
return Tree[root].max;
}
int mid = (Tree[root].left + Tree[root].right)>>1;
int ret = 0; //modify this
if(end <= mid)
ret = max(ret,RmaxQ(root<<1,start,end));
else if(start >= mid+1)
ret = max(ret,RmaxQ((root<<1)+1,start,end));
else
{
int a = RmaxQ(root<<1,start,mid);
int b = RmaxQ((root<<1)+1,mid+1,end);
ret = max(a,b);
}
return ret;
}
int main()
{
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 2836 Traversal(세그먼트 트리 + 이산화 + DP)제목 링크: 클릭하여 링크 열기 제목: n개의 서열을 줍니다. 한 개의 서열은 h입니다. 인접수의 차이가 h의 서열을 초과하지 않는 개수와% 9901을 구합니다. 사고방식: 고전적인 물문제는 분명히 d[i]로 a[i...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.