https://www.acmicpc.net/problem/2042

문제예시

1. 입력

5 2 2 // 입력숫자개수, 변경횟수, 출력횟수
1 //숫자입력
2 //숫자입력
3 //숫자입력
4 //숫자입력
5 //숫자입력
1 3 6 // 변경명령, 변경위치, 변경 후 숫자
2 2 5 // 출력명령, 구간 처음 위치, 구간 마지막 위치
1 5 2 // 변경명령, 변경위치, 변경 후 숫자
2 3 5 // 출력명령, 구간 처음 위치, 구간 마지막 위치 

2. 출력

17
12

3. 접근

• Fenwick Tree를 이용한 구간 합 구하기

1. fenwick tree를 구현한다
2. 본래 값을 저장할 배열을 생성
3. frewick tree의 값을 변경할때 (특정구간 변경후 값 - 특정구간 기존에 존재했던 값)을 특정위치 값이 포함된 모든 인덱스를 순회하며 값을 변경
4. 특정구간에 대한 값을 구하기 위해(M ~ N까지) (N까지 합) - (M - 1 까지의 합)을 구하면 됨

---

코드

struct FenwickTree {
    var size: Int
    var tree: [Int]
  
    init(size: Int) {
        self.size = size
        self.tree = Array(repeating: 0, count: size + 1)
    }
    
    func lsb(_ x: Int) -> Int {
        return x & -x
    }

    mutating func update(index: Int, diff: Int) {
        var idx = index
        while idx <= size {
            tree[idx] += diff
            idx += lsb(idx)
        }
    }

    func getSum(index: Int) -> Int {
        var sum = 0
        var idx = index
        while idx > 0 {
            sum += tree[idx]
            idx -= lsb(idx)
        }
        return sum
    }
    
    func rangeSum(from: Int, to: Int) -> Int {
        return getSum(index: to) - getSum(index: from - 1)
    }
}

let input = readLine()!.split(separator: " ").map { Int($0)! }
var fenwickTree = FenwickTree(size: input[0])
var array = [Int](repeating: 0, count: input[0] + 1)

for i in 1...input[0] {
    let value = Int(readLine()!)!
    fenwickTree.update(index: i, diff: value)
    array[i] = value
}

for _ in 0..<(input[1] + input[2]) {
    let orders = readLine()!.split(separator: " ").map { Int($0)! }
    if orders[0] == 1 {
        let idx = orders[1]
        let diff = orders[2] - array[idx]
        fenwickTree.update(index: idx, diff: diff)
        array[idx] = orders[2]
    } else {
        let result = fenwickTree.rangeSum(from: orders[1], to: orders[2])
        print(result)
    }
}