FenwickTree의 Swift 구현체

FenwickTree.swift

struct FenwickTree {
   var tree: [Int]
   var arr: [Int]
   init(size n: Int) {
       tree = Array(repeating: 0, count: n+1)
       arr = Array(repeating: 0, count: n)
   }

   func sum(_ pos: Int) -> Int {
       var ret = 0
       var pos = pos + 1
       while pos > 0 {
           ret += tree[pos]
           pos &= (pos-1)
       }

       return ret
   }

   mutating func add(at pos: Int, _ val: Int) {
       var pos = pos + 1
       while pos < tree.count {
           tree[pos] += val
           pos += (pos & -pos)
       }
   }

   mutating func replace(at pos: Int, val: Int) {
       let diff = val-arr[pos]
       arr[pos] = diff

       add(pos,diff)
   }
}