binary indexed tree(BIT, fenwick tree) 간단하게 배우기

1. 구조 binary indexed tree는 이름에서부터 2진법 인덱스 구조를 이용해서 구간 합 문제를 효과적으로 처리하기 위한 자료구조 point update, range sum을 효과적으로 처리하기 위한 자료구조 다음 그림이 binary indexed tree의 구조를 잘 보여주고 있다. 1) zero index가 아니라 binary indexed tree에서는 편의상 one index로 바꿔서 생각함 2) 데이터가 N개면 tree의 크기도 N이다. 3) tree의 각 index에는 어떤 값들이 저장되어 있는가? 1번 index에는 0번째 원소 1이 있고, 2번 index에는 0번 + 1번째 원소의 합 1+3 = 4가 저장 마찬가지로 3번 index에는 2번째 원소 11이 저장 4번 index에는..

• format_list_bulleted 알고리즘/세그먼트 트리
• · 2024. 2. 13.
• textsms

세그먼트 트리 응용단계 - 이분탐색과 콜라보1

1. 문제 1321번: 군인 (acmicpc.net) 1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 2. 풀이 문제를 잘 읽어보면 어떻게 풀어야할지 대충 보인다 군인은 군번대로 1번부대부터 차례대로 배치되고, 부대가 4, 3, 7 이렇게 있을때, 군번이 6번인 군인은 2번부대에 배치된다.. 왜냐하면 1번부대에 4번까지 배치하고 5번,6번 군인은 2번 부대에 배치되니까 그런데 부대의 인원이 줄어들거나 늘어날수 있고 그럴때 군인들이 처음부터 다시 배치한다는 것이다 이거는 이제 세그먼트 트리의 업데..

• format_list_bulleted 알고리즘/세그먼트 트리
• · 2023. 5. 9.
• textsms

세그먼트 트리 기본문제로 연습하며 재활(반복문, 재귀 연습)

1. 문제1 11143번: Beads (acmicpc.net) 11143번: Beads The first line of the input consists of a single number T, the number of games played. Each game start with a line describing B, P and Q, the number of boxes, put requests and query requests, respectively. Then follows P + Q lines with either P i a, saying www.acmicpc.net 2. 풀이 문제를 요약하자면 구간의 합을 구하는 세그먼트 트리 create_segment라는 함수는 만들필요가 없다 P라는 query가 ..

• format_list_bulleted 알고리즘/세그먼트 트리
• · 2023. 5. 5.
• textsms

반복문으로 구현하는 세그먼트 트리(iterative segment tree) 배우기

1. 반복문으로 구현하는 세그먼트 트리 세그먼트 트리 기본 버전은 재귀함수로 구현되어 있다 import math def create_segment(A,tree,tree_index,start,end): if start == end: tree[tree_index] = A[start] else: mid = (start+end)//2 create_segment(A,tree,2*tree_index,start,mid) create_segment(A,tree,2*tree_index+1,mid+1,end) tree[tree_index] = tree[2*tree_index] + tree[2*tree_index+1] def query_sum(tree,tree_index,start,end,left,right): if lef..

• format_list_bulleted 알고리즘/세그먼트 트리
• · 2023. 5. 4.
• textsms

세그먼트 트리 응용 - 2개의 쿼리를 동시에 수행할 수 있는 2차원 세그먼트 트리

1. 문제 18436번: 수열과 쿼리 37 (acmicpc.net) 18436번: 수열과 쿼리 37 길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤ www.acmicpc.net 구간에서 짝수의 개수를 출력하거나, 홀수의 개수를 출력하거나, 값을 바꾸는 쿼리를 수행하는 세그먼트 트리를 만드는 문제 2. 풀이 조금 응용해서, 세그먼트 트리를 2차원으로 구성해보자 [[0,0] for _ in range(n+1)] 형태로 tree[tree_index][0]은 구간의 짝수의 개수, tree[tree_index][1]..

• format_list_bulleted 알고리즘/세그먼트 트리
• · 2022. 12. 15.
• textsms

세그먼트 트리 응용 - XOR 연산을 수행하는 트리

1. 문제 14245번: XOR (acmicpc.net) 14245번: XOR 첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄 www.acmicpc.net 구간에 어떤 수를 XOR하는 쿼리와 어떤 index에 대응하는 원소를 출력하는 쿼리를 수행하는 문제 2. 풀이 구간에 수를 연산하니까 느리게 갱신되는 세그먼트 트리가 필요할 것 같고 index 하나 원소만 출력하는 트리는 이미 배웠으니까 def create_segment(A,tree,tree_index,A_start,A_end): if A_start == A_end: tree[..

• format_list_bulleted 알고리즘/세그먼트 트리
• · 2022. 12. 15.
• textsms