백준 2042 구간 합 구하기
23 Jun 2021https://www.acmicpc.net/problem/2042
수열이 주어졌을 때 수열의 부분 구간에 대해 구간 합을 구하는 문제이다. 이 때 수열의 값은 변할 수 있다. 만약 수열의 값이 변하지 않는다면 간단하게 누적합의 차로 구간 합을 구할 수 있다. 하지만 수열의 값이 변하게 될 경우 해당 수를 포함하는 모든 누적합의 값이 변해야해서 update할때마다 O(n) 의 시간이 걸리게 된다.
그렇기 때문에 앞에서 정리한 세그먼트 트리를 활용할 것이다. 구간합을 구하는 문제이기 때문에 fenwick트리와 세그먼트 트리 중 어떤 것을 사용해도 상관은 없다. 유의할 점으로는 정답이 Int64범위이기 때문에 Clonglong으로 타입을 선언해주었다.
- 전체 코드
struct Segment {
private var arr:[CLongLong]
private var seg:[CLongLong]
public mutating func calcDiff(index: Int, value: CLongLong) -> CLongLong {
let previous = arr[index]
arr[index] = value
return value - previous
}
public mutating func update(start: Int, end: Int, node: Int, index: Int, diff: CLongLong) {
if index < start || index > end {
return
}
seg[node] += diff
if start == end {
return
}
let mid = (start+end)/2
update(start: start, end: mid, node: 2*node, index: index, diff: diff)
update(start: mid+1, end: end, node: 2*node+1, index: index, diff: diff)
}
public func sum(start: Int, end: Int, node: Int, left: Int, right: Int) -> CLongLong {
if left > end || right < start {
return 0
}
if left <= start && end <= right {
return seg[node]
}
let mid = (start+end)/2
return sum(start: start, end: mid, node: 2*node, left: left, right: right) + sum(start: mid+1, end: end, node: 2*node+1, left: left, right: right)
}
private mutating func makeSeg(start: Int, end: Int, node: Int) -> CLongLong {
if start == end {
seg[node] = arr[start]
}
else {
let mid = (start+end)/2
seg[node] = makeSeg(start: start, end: mid, node: 2*node) + makeSeg(start: mid+1, end: end, node: 2*node+1)
}
return seg[node]
}
init(arr: [CLongLong]) {
self.arr = arr
seg = Array(repeating: 0, count: 4*arr.count)
makeSeg(start: 0, end: arr.count-1, node: 1)
}
}
let nmk = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nmk[0], m = nmk[1], k = nmk[2]
var arr:[CLongLong] = Array(repeating: -1, count: n)
for i in 0..<n {
arr[i] = CLongLong(String(readLine()!))!
}
var segtree = Segment(arr: arr)
var str = ""
for _ in 1...m+k {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
if line[0] == 1 {
let diff = segtree.calcDiff(index: line[1]-1, value: CLongLong(line[2]))
segtree.update(start: 0, end: n-1, node: 1, index: line[1]-1, diff: diff)
}
else {
str += "\(segtree.sum(start: 0, end: n-1, node: 1, left: line[1]-1, right: line[2]-1))\n"
}
}
print(str)