BOJ 2042 구간 합 구하기.

https://www.acmicpc.net/problem/2042
시간 2초, 메모리 256MB
input :

• N M K(1 ≤ N ≤ 1,000,000)(1 ≤ M ≤ 10,000)(1 ≤ K ≤ 10,000)
• N+1번째 줄까지 N개의 수
• N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, (그냥 m + k 만큼의 입력이 들어옴)
• a가 1인 경우 b(1 ≤ b ≤ N)번째 수를 c로 바꾸고
• a가 2인 경우에는 b(1 ≤ b ≤ N)번째 수부터 c(b ≤ c ≤ N)번째 수까지의 합을 구하여 출력

output :

• 첫째 줄부터 K줄에 걸쳐 구한 구간의 합을 출력

---

펜윅 트리를 쓸 때가 되었다. 뚜둔!

기본적인 함수 add, sum 을 작성 한다.
add의 경우 맨 처음 초기화 하기 위한 함수이고, sum 의 경우 구간합을 구하기 위함이다.

def add(idx, num):
    # idx 에 해당하는 놈이 추가 된다.
    while idx < len(tree):
        tree[idx] += num
        idx += (idx & -idx)

입력 받은 idx 에다가 num 을 추가해준다. 그리고 펜윅 트리의 경우 부분합을 저장하는 구조이기 때문에 +를 이용해준다.

def sum(idx):
    ret = 0
    while idx >= 1:
        ret += tree[idx]
        idx &= (idx - 1)
    return ret

가장 끝 인덱스에서 부터 마지막 비트를 빼는 방식으로 인덱스가 줄어든다. 그리고 마지막엔 꼭 ret를 리턴하자.

추가적으로 만들어야 하는 update함수. m + k 번 입력을 받는 도중에 이용하는데. 원래 a배열에 존재하는 값을 모든 부분합에서 빼주고 새로 입력받는 값을 추가해 주어야 한다.
그리고 이때 입력 받는 변수를 a, b, c로 입력을 받으면 배열의 변수와 동일하기 때문에 다른것을 이용해야 한다.

def update(idx, num):
    pivot = a[idx]
    a[idx] = num
    while idx < len(tree):
        tree[idx] -= pivot
        tree[idx] += num
        idx += (idx & -idx)

그리고 update 할 때 a배열의 값도 바꾸어 주어야 한다.

import sys

def add(idx, num):
    # idx 에 해당하는 놈이 추가 된다.
    while idx < len(tree):
        tree[idx] += num
        idx += (idx & -idx)

def sum(idx):
    ret = 0
    while idx >= 1:
        ret += tree[idx]
        idx &= (idx - 1)
    return ret

def update(idx, num):
    pivot = a[idx]
    a[idx] = num
    while idx < len(tree):
        tree[idx] -= pivot
        tree[idx] += num
        idx += (idx & -idx)


n, m, k = map(int, sys.stdin.readline().split())
tree = [0] * (n + 1)
a = [0] * (n + 1)

for i in range(n):
    temp = int(sys.stdin.readline())
    a[i + 1] = temp
    add(i + 1, temp)

for i in range(m + k):
    k, b, c = map(int, sys.stdin.readline().split())
    if k == 1:
        update(b, c)
    else:
        print(sum(c) - sum(b - 1))