Add segment tree implementation

1 files changed, 41 insertions, 2 deletions

diff --git a/sd.go b/sd.go
index efe442c..743aaa6 100644
--- a/sd.go
+++ b/sd.go
@@ -9,6 +9,45 @@ import (
 
 var file = flag.String("f", "cards", "cards file")
 
+var seg = []int{}
+
+func build(a *[]int, l int, r int, n int) {
+	if l == r {
+		seg[n] = (*a)[l]
+		return
+	}
+	m := (l + r) >> 1
+	build(a, l, m, n<<1)
+	build(a, m+1, r, n<<1|1)
+	seg[n] = seg[n<<1] + seg[n<<1|1]
+}
+
+func update(x int, v int, l int, r int, n int) {
+	if l == r {
+		seg[n] += v
+		return
+	}
+	m := (l + r) >> 1
+	if x <= m {
+		update(x, v, l, m, n<<1)
+	} else {
+		update(x, v, m+1, r, n<<1|1)
+	}
+	seg[n] = seg[n<<1] + seg[n<<1|1]
+}
+
+func query(v int, l int, r int, n int) (int, int) {
+	if l == r {
+		return seg[n], n
+	}
+	m := (l + r) >> 1
+	if seg[n<<1] < v {
+		return query(v, l, m, n<<1)
+	} else {
+		return query(v-seg[n<<1], m+1, r, n<<1|1)
+	}
+}
+
 func main() {
 	flag.Parse()
 
@@ -22,7 +61,7 @@ func main() {
 
 	for {
 		fmt.Println("hello world")
-		
+
 		var b []byte = make([]byte, 1)
 		os.Stdin.Read(b)
 		if string(b) == 'y' {
@@ -30,7 +69,7 @@ func main() {
 		} else if string(b) == 'n' {
 
 		} else {
-			
+
 		}
 	}
 }