ACM 데이터 구조 입문

동료 에 게 쓴 것 을 가 는 김 에 스스로 정리 하 다.
본 고 는 기초 적 인 acm 가 사용 할 수 있 는 데이터 구 조 를 총 결 하 였 다.
창고, 대열, 그리고 수집 등 기초 지식 을 생략 하 였 다.
RMQ
장점: 복잡 도가 낮 아 틀 리 기 쉽 지 않 습 니 다.배가 되 는 사상 이 매우 좋다.
단점: 수정 작업 은 지원 되 지 않 으 며 사용 처 는 적 습 니 다.
초급 문제
진급 문제 추천 HDU 5289
트 리 배열
보기 에는 간단 하지만 실제로는 매우 큰 데이터 구 조 를 사용 합 니 다. 선분 트 리 보다 작성 하기 어렵 지만 선분 트 리 를 대체 할 수 있 는 경우 가 많 습 니 다. 성 가 는 매우 높 습 니 다.
더 좋 은 것 은 같은 방법 에서 선분 수 는 종종 나무 모양 의 배열 보다 느리다 는 것 이다.
초급 입문 본 고 는 군말 이 아니다.
진급 문제 추천: poj 3468 (원래 선분 트 리 의 제목 이지 만 가장 빠 른 프로그램 은 모두 트 리 배열)
선분 수
슈퍼 무적의 제목, 그 당시 고등학교 1 학년 선분 수 는 많은 커 브 길 을 걸 었 습 니 다. 선분 수 는 너무 많은 표기 법 이 있 기 때문에 하나의 표기 법 을 볼 때마다 하나의 표기 법 이 많아 서 더욱 막막 해 졌 습 니 다. 그래서 추천 하 는 방법 은 선분 수 를 쓰 는 것 을 배 운 다음 에 다른 표기 법 을 보지 않 으 면 많은 시간 을 절약 할 수 있 습 니 다.
초급 고전 제목: poj 2777
진급 문제: poj 3468 (본 문제 AC 후 표지 의 역할 을 초보 적 으로 이해 할 수 있 음)
최종 제목: poj 1177 (초보 자 는 시도 하지 않 고 시간 낭비)
선분 트 리 의 서법 이 너무 많 기 때문에 본 고 는 자신의 서법 을 붙 여 지도 한다.

#include 
#include 
#include 
#include 
#define intt long long
#define rep(i, j, k) for(int i = j; i <= k; i++)

using namespace std;

int m, a[100009];
intt n, l[2000009], r[2000009], add[2000009], sum[2000009];

void build (int x, intt L, intt R)
{
	l[x] = L, r[x] = R;
	if (L == R)
	{
		sum[x] = a[L];
		add[x] = 0;
		return;
	}
	intt mid = (L + R) >> 1;
	build (2 * x, L, mid);
	build (2 * x + 1,mid + 1, R);
	sum[x] = sum[2 * x] + sum[2 * x + 1];
	add[x] = 0;
	return;
}

intt ask (int x, intt L, intt R)
{
	if (L > r[x] || R < l[x])
		return 0;
	if (L <= l[x] && r[x] <= R)
		return sum[x] + add[x] * (r[x] - l[x] + 1);
	add[2 * x] += add[x];
	add[2 * x + 1] += add[x];
	add[x] = 0;
	sum[x] = sum[2 * x] + add[2 * x] * ( r[2 * x] - l[2 * x] + 1) + sum[2 * x + 1] + add[2 * x + 1] * (r[2 * x + 1] - l[2 * x + 1] + 1);
	return ask (2 * x, L, R) + ask (2 * x + 1, L, R);
}

void Add (int x, intt L, intt R, intt num)
{
	if (L > r[x] || R < l[x])
		return;
	if (L <= l[x] && r[x] <= R)
	{
		add[x] += num;
		return;
	}
	add[2 * x] += add[x];
	add[2 * x + 1] += add[x];
	add[x] = 0;
	Add (2 * x, L, R, num);
	Add (2 * x + 1, L, R, num);
	sum[x] = sum[2 * x] + add[2 * x] * ( r[2 * x] - l[2 * x] + 1) + sum[2 * x + 1] + add[2 * x + 1] * (r[2 * x + 1] - l[2 * x + 1] + 1);
	return;
}

int main()
{
	while (scanf ("%lld%d", &n, &m) == 2 && n != 0)
	{
		rep (i, 1, n)
			scanf ("%d", &a[i]);
		build (1, 1, n);
		while (m--)
		{
			getchar ();
			char ch;
			scanf ("%c", &ch);
			if (ch == 'Q')
			{
				intt x, y;
				scanf ("%lld%lld", &x, &y);
				printf ("%lld
", ask (1, x, y));
			}
			else
			{
				intt x, y, z;
				scanf ("%lld%lld%lld", &x, &y, &z);
				Add (1, x, y, z);
			}
		}
	}
	return 0;
}

밸 런 스 트 리
밸 런 스 트 리 의 표기 법 은 여러 가지 가 있 고 종류 도 많 습 니 다. 가장 유명한 것 은 당연히 빨간색 과 검은색 나무 입 니 다. 그러나 실제 경기 에서 이런 것들 을 시험 해 본 적 이 없습니다. 이렇게 많은 밸 런 스 트 리 의 역할 차이 가 많 지 않 고 상수 의 차이 만 있 기 때 문 입 니 다. 예 를 들 어 SBT 는 쓰기 가 매우 어렵 기 때문에 상수 상의 최적화 와 바 꾸 었 습 니 다. 그리고 복잡 도 를 확보 하기 만 하면상 수 는 너무 고민 할 필요 가 없습니다. 제 가 가장 좋아 하 는 것 은 splay 입 니 다. splay 기능 이 매우 강하 기 때문에 상수 가 매우 크 지만 대부분 사용 하기에 충분 하기 때문에 초보 자 들 이 splay 를 먼저 파악 하 는 것 을 권장 합 니 다. 그리고 treap 같은 것 은 잠시 내 버 려 두 어도 됩 니 다. 고등학교 때 각종 균형 트 리 를 배 우 는 데 많은 시간 을 낭 비 했 습 니 다. 나중에 사람들 이 제 교훈 을 받 아들 이 기 를 바 랍 니 다.
문자열 데이터 구조
Trie
전설의 알파벳 나 무 는 쓰기 가 어렵 지 않다.파 촉 의 교과서 에는 상세 한 해석 이 있다.
AC 자동 동기
이해 하기 어렵 지 않 습 니 다. 훈련 안내 서 는 이미 아주 잘 말 했 습 니 다.
접미사 배열
본인 이 알 고 있 었 는데 까 먹 었 어 요.이것 은 확실히 번거롭다.구 덩이 를 남 겨 두 어 라.
본 고 는 단지 학습 의 요강 일 뿐 구체 적 인 학습 은 개인 을 봐 야 한다. 본인 이 생각 하 는 가장 좋 은 방법 은 파 촉 의 과제 와 유 여가 의 알고리즘 경 기 를 보고 전형 적 인 훈련 지침 에 입문 한 다음 에 해당 하 는 poj 입문 문 제 를 찾 아 한 다음 에 문 제 를 늘 려 익숙 한 수준 에 이 르 는 것 이다.
전체적으로 보면 초급 데이터 구조 가 이렇게 많 고 개인 적 으로 선분 나무 가 가장 중요 하 다 고 생각 하기 때문에 반드시 깊이 이해 하고 연습 을 많이 해 야 한다.