데이터 구조 (선분 트 리 입문 상세 소개) (단점 업데이트) (구조 체)
8180 단어 데이터 구조
HDU 1166 적군 포진 (단점 업데이트) (구조 체 형식)
제목: T, T 테스트 샘플 입력
매번 n 을 입력 할 때마다 n 개의 데이터 가 있다 는 것 을 설명 합 니 다.n 개의 데 이 터 를 입력 하 십시오.
Query a b 입력: a b 사이 의 합 을 조회 합 니 다.
Add i x 입력: i 에 x 개 수 를 추가 합 니 다.
Sub i x 입력: i 에서 x 개 삭제
입력 끝
예:
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3： 출력 6 (1 + 2 + 3)
Add 3 6： 배열 이 1, 2, 9, 4, 5, 6, 7, 8, 9, 10 으로 바 뀌 었 습 니 다.
Query 2 7： 출력 33 (2 + 9 + 4 + 5 + 6 + 7)
Sub 10 2： 1, 2, 9, 4, 5, 6, 7, 8, 9, 8.
Add 6 3： 1, 2, 9, 4, 5, 9, 7, 8, 9, 8.
Query 3 10: 출력 59 (9 + 4 + 5 + 9 + 7 + 8 + 9 + 8)
End ： 끝나다
건축 수: 선분 나무의 장점 은 ★ 가능 한 것 과 미리 계산 하 는 것 이다 (예 를 들 어 결점 16, 17, 9, 10, 11 의 합 을 계산 하려 면 출력 결점 2 만 사용 하면 된다. 조회 할 때 추가 하 는 과정 을 줄 였 다)
55（1）
/ \
15（2） 40（3）
/ \ / \
6（4） 9（5） 21（6） 19（7）
/ \ / \ / \ / \
3（8） 3（9） 4（10） 5（11） 13（12） 8（13） 9（14） 10（15）
/ \ 【3】 【4】 【5】 / \ 【8】 【9】 【10】
1（16） 2（17） 6（18） 7（19）
【1】 【2】 【6】 【7】
tip: () 중 결점 번호, [] 중 범위 아래 표 시 됩 니 다. 보통 입력 한 수치 와 일부 범위 내의 합 입 니 다.
모든 나무 결점:
#define ll rt<<1
#define rr rt<<1|1
using namespace std;
const int maxn=50010;
struct Tree{
int l,r;//sum
int sum;
}tree[maxn<<2];① 라인 트 리 만 들 기:
void PushUP(int rt){
tree[rt].sum= tree[ll].sum +tree[rr].sum;
}
void build(int l,int r,int rt)
{
tree[rt].l=l; tree[rt].r=r;
if(l==r){
scanf("%d",&tree[rt].sum);
return ;
}
int m=(l+r)>>1;
build(l,m,ll); //ll -> #define ll rt<<1
build(m+1,r,rr);//rr -> #define rr rt<<1|1
PushUP(rt);
}트 리 를 만 드 는 범위 의 가장 왼쪽 값 (기본 값 은 1 부터), 가장 오른쪽 값 (입력 한 n), 트 리 의 총 뿌리 결산 점 (기본 값 은 1 을 총 뿌리 결산 점) build (1, n, 1) 을 입력 하 십시오.
tree[ rt ].l = l ; tree[ rt ].r = r ;
전체 루트 노드 rt = 1 (1).그러면 tree [1] 의 가장 왼쪽 은 1 이 고 가장 오른쪽 은 n 이다. 즉, 결점 (1) 에 포 함 된 것 과 1 에서 n 까지 의 것 이다.
그리고 각각 좌우 양쪽 으로 나 누 어 나 무 를 지 었 다.
build( l , m , rt * 2 );
왼쪽 (1, (n + 1) / 2 ）
그러면 왼쪽 뿌리 노드 는 rt = 2 * rt = 2 (2) 。그러면 tree [2] 의 가장 왼쪽 은 1 이 고 가장 오른쪽 은 (n + 1) / 2 이다.
계속 좌우 로 나 무 를...
build( m+1 , r , rt * 2+1 );
오른쪽
PushUP( rt );
위의 두 단 계 를 실행 한 후에 뿌리 노드 rt 는 좌우 노드 가 있 습 니 다. 그러면 rt 의 값 은 rt * 2 와 rt * 2 + 1 의 합 입 니 다.
if ( l == r )
l = = r 까지 범 위 를 한 점 으로 축소 한 다 는 뜻 입 니 다. 그러면 이 점 에서 값 을 입력 하 십시오.
★ 왜 나무 밑바닥 의 잎 사 귀 노드 가 1, 2, 6 인가 ，7 이 아니 라 1, 2, 3, 4?
나 무 를 만 드 는 과정 이 반 으로 접 혀 있 기 때문에 배열 [10] = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.
반, 반, 하나, 둘, 셋, 45, 반, 67, 8910 으로 나 뉜 다.
그리고 계속 양쪽 으로 나 눕 니 다. 끝까지 나 눌 때 1, 2 를 맨 밑 에 놓 고 위로 올 립 니 다.
(공교롭게도) 반반, 12345 와 678910 은 같은 효과 가 있 기 때문에 가장 밑바닥 잎 노드 의 값 은 1, 2, 6, 7 이다.
★ 좌우 에 나 무 를 세 우 는 순 서 를 바 꿀 수 있 나 요?
아니요. 입력 한 순 서 는 왼쪽 에서 오른쪽으로 하기 때문에 먼저 왼쪽으로 탐색 하고 반 으로 접어 서 왼쪽 밑 으로 탐색 하 며 첫 번 째 수 를 입력 한 다음 에 끝까지 탐색 하고 다른 수 를 순서대로 입력 해 야 합 니 다. 이렇게 하면 순서대로 나무 에 들 어 가 는 것 입 니 다.
좌우 로 나 무 를 만 드 는 순서 가 바 뀌 면 입력 한 수 는 원래 의 순서 가 아니다.
★ 수치 가 비교적 많 습 니 다. 여러 번 도와 주세요. 세 가지 유형 으로 나 눌 수 있 습 니 다.
(1) rt 이 값 은 노드 번호 입 니 다.
(2) tree [rt]. sum 이 값 은 입력 한 값 과 입력 한 값 의 부분 과
(3) tree [rt]. l, tree [rt]. r 의 값 은 좌우 범위, 즉 1 ~ n 의 수 이다.
② 업데이트 작업
void update(int p,int add,int rt)
{
if( tree[rt].l == tree[rt].r ) {
tree[rt].sum += add;
return ;
}
int m = ( tree[rt].l + tree[rt].r ) >>1;
if(p <= m) update( p, add, ll );
else update( p, add, rr );
PushUP(rt);
}입력: 변경 할 값 의 위치 p, 추가 할 값 add, 총 루트 노드 rt (기본 1) 루트 노드 rt 의 좌우 범위 값 이 같 을 때 이 조회 점 입 니 다. 루트 노드 이 값 + add
업데이트 할 값 이 rt 의 좌우 범위 의 중간 값 보다 작다 면, 업데이트 할 위 치 는 rt 의 왼쪽 에 있 고, 반대로 오른쪽 에 있 습 니 다.
위의 업 데 이 트 를 마 친 후에 값 을 다시 계산 합 니 다.
③ 조회 조작
int query(int L,int R,int rt)
{
if(L <= tree[rt].l && tree[rt].r <= R)
return tree[rt].sum;
int m = ( tree[rt].l + tree[rt].r )>>1;
if(R <= m) return query(L,R,ll);
else if(L > m) return query(L,R,rr);
else return query(L,R,ll) + query(L,R,rr);
} 입력: 검색 할 좌우 범위, L ~ R (L, R 포함) 및 총 루트 노드 rt
만약 에 찾 으 려 는 루트 노드 범위 L R 에 마침 결점 rt 왼쪽 에서 오른쪽으로 포함 되 어 있다 면 다행 입 니 다. 결점 rt 왼쪽 에서 오른쪽 까지 의 값 sum 은 이미 계산 되 었 기 때문에 더 이상 찾 지 않 아 도 됩 니 다. 바로 이것 과 같 습 니 다.
m
（ tree[ rt ].l ） |_______|_______|（ tree[ rt ].r）
（L）|_____________________|（R）
[상태 1 (왼쪽 과 오른쪽 모두 안에 포함 되 지 않 은 것 이 조금 남 았 습 니 다. 아래 의 다른 상태 일 수도 있 습 니 다. 그리고 상태 4 로 통합 합 니 다)]
그리고 보면 R 이 m 보다 작 으 면...
m
（ tree[ rt ].l ） |________|________|（ tree[ rt ].r）
（ tree[ rt * 2 ].l ） |________|（ tree[ rt * 2 ].r ）
（L）|_____________________|（R）
[상태 2: 왼쪽으로 범 위 를 좁 히 기 (이 그림 은 오른쪽 부분 만 고려 하고 왼쪽 부분 은 다른 상태 일 수 있 습 니 다. 그리고 상태 4 로 통합)] L 이 m 보다 크 면
m
（ tree[ rt ].l ） |______|______|（ tree[ rt ].r）
（ tree[ rt * 2 +1 ].l ） |______|（ tree[ rt * 2 +1 ].r）
（L）|_____________________|（R）
[상태 3: 오른쪽으로 범 위 를 축소 합 니 다 (이 그림 은 왼쪽 부분 만 고려 하고 오른쪽 부분 은 다른 상태 일 수 있 습 니 다. 그리고 상태 4 로 통합 합 니 다)] 다른 상황:
m m
（ tree[ rt ].l ） |______________|_____________|（ tree[ rt ].r） （ tree[ rt ].l ） |________|________|（ tree[ rt ].r）
|______________||_____________| |________||________|
（L）|_____________________|（R） （L）|_____________________|（R） 【 상태 4: 좌우 추가 가 필요 합 니 다. 】 [상태 4 의 하위 상태 (그리고 오른쪽 은 안 그 릴 게 요)]
다른 상태 가 있 냐 는 질문 이 있 을 수 있 습 니 다.
m
（ tree[ rt ].l ） |______|______|（ tree[ rt ].r）
(L) | | (R) ★ 그렇다면 [상태 3] 과 같 지 않 나 요?
답: 이 부분 은 존재 하지 않 습 니 다. 우 리 는 이 부분 을 고려 하지 않 습 니 다. 처음에 범위 가 가장 큰 1 ~ n 이 었 을 것 입 니 다. 모든 상황 을 포함 하고 있 었 기 때 문 입 니 다. 그러면 [상태 4] 는 우리 가 원 하 는 부분 으로 계속 축소 되 었 습 니 다.
이런 상황 이 있 지만 이 상황 은 바로 [상태 2] 와 [상태 3] 가 버 린 부분 입 니 다. 두 번 째 줄 을 보 세 요. 우리 의 절반 조작 은 이미 버 리 고 원 하지 않 습 니 다.
④ 주 함수:
int main()
{
int cas=1,T,n;
scanf("%d",&T);
while(T--)
{
printf("Case %d:
",cas++);
scanf("%d",&n);
build(1,n,1);
/*
for(int i=1;i<=2*n;i++){
printf("%d %d %d
",tree[i].l , tree[i].sum , tree[i].r);
}
for(int i=1;i<=3*n;i++)
printf("%d--",sum[i]);*/
char op[10];
while(scanf("%s",op)){
if(op[0]=='E') //
break;
int a,b;
scanf("%d%d",&a,&b);
if(op[0]=='Q') //
printf("%d
",query(a,b,1));
else if(op[0]=='S') //
update(a,-b,1);
else if(op[0]=='A') //
update(a,b,1);
}
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
