Segment Ağacı ve Fenwick Ağacı

package main

import "fmt"

type PrefixSum struct {
	prefix []int
	data   []int
}

func NewPrefixSum(data []int) *PrefixSum {
	p := &PrefixSum{data: append([]int(nil), data...), prefix: make([]int, len(data)+1)}
	for i, v := range data {
		p.prefix[i+1] = p.prefix[i] + v
	}
	return p
}

// Query: [lo, hi) aralığının toplamı — O(1)
func (p *PrefixSum) Query(lo, hi int) int {
	return p.prefix[hi] - p.prefix[lo]
}

// Update: O(n) — sonraki tüm önekler bozulur
func (p *PrefixSum) Update(i, value int) {
	diff := value - p.data[i]
	p.data[i] = value
	for j := i + 1; j < len(p.prefix); j++ {
		p.prefix[j] += diff
	}
}

func main() {
	data := []int{3, 1, 4, 1, 5, 9, 2, 6}
	ps := NewPrefixSum(data)

	fmt.Println("dizi:", data)
	fmt.Println("önek toplamları:", ps.prefix)
	fmt.Println()

	for _, r := range [][2]int{{0, 8}, {2, 6}, {5, 6}, {3, 3}} {
		fmt.Printf("toplam[%d..%d) = %d\n", r[0], r[1], ps.Query(r[0], r[1]))
	}

	fmt.Println()
	ps.Update(2, 10) // 4 → 10
	fmt.Println("indeks 2 → 10 güncellendi")
	fmt.Println("yeni önekler:", ps.prefix)
	fmt.Println("toplam[2..6) =", ps.Query(2, 6))

	fmt.Println()
	fmt.Println("sorgu: O(1) — mükemmel")
	fmt.Println("güncelleme: O(n) — sorun burada")
}

package main

import "fmt"

type SegmentTree struct {
	tree   []int
	n      int
	visits int // sorgu sırasında ziyaret edilen düğüm sayısı
}

func NewSegmentTree(data []int) *SegmentTree {
	n := len(data)
	st := &SegmentTree{tree: make([]int, 4*n), n: n} // 4n her zaman yeterlidir
	if n > 0 {
		st.build(data, 1, 0, n-1)
	}
	return st
}

// build: O(n) — her düğüm bir kez hesaplanır
func (st *SegmentTree) build(data []int, node, lo, hi int) {
	if lo == hi {
		st.tree[node] = data[lo]
		return
	}
	mid := (lo + hi) / 2
	st.build(data, 2*node, lo, mid)
	st.build(data, 2*node+1, mid+1, hi)
	st.tree[node] = st.tree[2*node] + st.tree[2*node+1]
}

// Query: [l, r] kapalı aralığının toplamı — O(log n)
func (st *SegmentTree) Query(l, r int) int {
	if st.n == 0 || l > r {
		return 0
	}
	st.visits = 0
	return st.query(1, 0, st.n-1, l, r)
}

func (st *SegmentTree) query(node, lo, hi, l, r int) int {
	st.visits++
	if r < lo || hi < l {
		return 0 // tamamen dışarıda
	}
	if l <= lo && hi <= r {
		return st.tree[node] // tamamen içeride: hazır cevap
	}
	mid := (lo + hi) / 2
	return st.query(2*node, lo, mid, l, r) + st.query(2*node+1, mid+1, hi, l, r)
}

// Update: tek noktayı günceller — O(log n)
func (st *SegmentTree) Update(i, value int) {
	if st.n == 0 {
		return
	}
	st.update(1, 0, st.n-1, i, value)
}

func (st *SegmentTree) update(node, lo, hi, i, value int) {
	if lo == hi {
		st.tree[node] = value
		return
	}
	mid := (lo + hi) / 2
	if i <= mid {
		st.update(2*node, lo, mid, i, value)
	} else {
		st.update(2*node+1, mid+1, hi, i, value)
	}
	st.tree[node] = st.tree[2*node] + st.tree[2*node+1] // geri dönerken güncelle
}

func main() {
	data := []int{3, 1, 4, 1, 5, 9, 2, 6}
	st := NewSegmentTree(data)

	fmt.Println("dizi:", data)
	fmt.Println("toplam:", st.Query(0, 7))
	fmt.Println()

	for _, r := range [][2]int{{0, 7}, {2, 5}, {5, 5}, {0, 3}, {4, 7}} {
		sum := st.Query(r[0], r[1])
		fmt.Printf("toplam[%d..%d] = %-3d (ziyaret edilen düğüm: %d)\n", r[0], r[1], sum, st.visits)
	}

	fmt.Println()
	st.Update(2, 10) // 4 → 10, fark +6
	fmt.Println("indeks 2: 4 → 10")
	fmt.Println("yeni toplam[0..7] =", st.Query(0, 7), "(önceki 31 + 6)")
	fmt.Println("yeni toplam[2..5] =", st.Query(2, 5))

	st.Update(7, 0)
	fmt.Println()
	fmt.Println("indeks 7: 6 → 0")
	fmt.Println("toplam[6..7] =", st.Query(6, 7))
	fmt.Println("toplam[0..7] =", st.Query(0, 7))
}

package main

import "fmt"

type Op struct {
	name    string
	combine func(a, b int) int
	neutral int
}

type SegmentTree struct {
	tree []int
	n    int
	op   Op
}

func NewSegmentTree(data []int, op Op) *SegmentTree {
	st := &SegmentTree{tree: make([]int, 4*len(data)), n: len(data), op: op}
	for i := range st.tree {
		st.tree[i] = op.neutral
	}
	if st.n > 0 {
		st.build(data, 1, 0, st.n-1)
	}
	return st
}

func (st *SegmentTree) build(data []int, node, lo, hi int) {
	if lo == hi {
		st.tree[node] = data[lo]
		return
	}
	mid := (lo + hi) / 2
	st.build(data, 2*node, lo, mid)
	st.build(data, 2*node+1, mid+1, hi)
	st.tree[node] = st.op.combine(st.tree[2*node], st.tree[2*node+1])
}

func (st *SegmentTree) Query(l, r int) int {
	if st.n == 0 || l > r {
		return st.op.neutral
	}
	return st.query(1, 0, st.n-1, l, r)
}

func (st *SegmentTree) query(node, lo, hi, l, r int) int {
	if r < lo || hi < l {
		return st.op.neutral
	}
	if l <= lo && hi <= r {
		return st.tree[node]
	}
	mid := (lo + hi) / 2
	return st.op.combine(
		st.query(2*node, lo, mid, l, r),
		st.query(2*node+1, mid+1, hi, l, r),
	)
}

func (st *SegmentTree) Update(i, value int) {
	st.update(1, 0, st.n-1, i, value)
}

func (st *SegmentTree) update(node, lo, hi, i, value int) {
	if lo == hi {
		st.tree[node] = value
		return
	}
	mid := (lo + hi) / 2
	if i <= mid {
		st.update(2*node, lo, mid, i, value)
	} else {
		st.update(2*node+1, mid+1, hi, i, value)
	}
	st.tree[node] = st.op.combine(st.tree[2*node], st.tree[2*node+1])
}

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	if a < 0 {
		return -a
	}
	return a
}

func main() {
	data := []int{12, 8, 20, 4, 16, 24}

	ops := []Op{
		{"toplam", func(a, b int) int { return a + b }, 0},
		{"minimum", func(a, b int) int { return min(a, b) }, 1 << 60},
		{"maksimum", func(a, b int) int { return max(a, b) }, -(1 << 60)},
		{"OBEB", gcd, 0},
	}

	fmt.Println("dizi:", data)
	fmt.Println()
	fmt.Printf("%-10s %10s %10s %10s\n", "işlem", "[0..5]", "[1..3]", "[2..4]")
	for _, op := range ops {
		st := NewSegmentTree(data, op)
		fmt.Printf("%-10s %10d %10d %10d\n",
			op.name, st.Query(0, 5), st.Query(1, 3), st.Query(2, 4))
	}

	// Güncelleme her işlemde çalışır
	fmt.Println()
	minTree := NewSegmentTree(data, ops[1])
	fmt.Println("minimum[0..5] =", minTree.Query(0, 5))
	minTree.Update(3, 100) // en küçük değer olan 4'ü büyüt
	fmt.Println("indeks 3: 4 → 100")
	fmt.Println("yeni minimum[0..5] =", minTree.Query(0, 5))
}

package main

import "fmt"

type LazySegmentTree struct {
	tree []int
	lazy []int
	n    int
}

func NewLazy(data []int) *LazySegmentTree {
	st := &LazySegmentTree{
		tree: make([]int, 4*len(data)),
		lazy: make([]int, 4*len(data)),
		n:    len(data),
	}
	if st.n > 0 {
		st.build(data, 1, 0, st.n-1)
	}
	return st
}

func (st *LazySegmentTree) build(data []int, node, lo, hi int) {
	if lo == hi {
		st.tree[node] = data[lo]
		return
	}
	mid := (lo + hi) / 2
	st.build(data, 2*node, lo, mid)
	st.build(data, 2*node+1, mid+1, hi)
	st.tree[node] = st.tree[2*node] + st.tree[2*node+1]
}

// push: bekleyen güncellemeyi çocuklara aktarır
func (st *LazySegmentTree) push(node, lo, hi int) {
	if st.lazy[node] == 0 {
		return
	}
	st.tree[node] += st.lazy[node] * (hi - lo + 1) // aralıktaki her elemana eklenir
	if lo != hi {
		st.lazy[2*node] += st.lazy[node]
		st.lazy[2*node+1] += st.lazy[node]
	}
	st.lazy[node] = 0
}

// RangeAdd: [l, r] aralığındaki her elemana delta ekler — O(log n)
func (st *LazySegmentTree) RangeAdd(l, r, delta int) {
	if st.n == 0 || l > r {
		return
	}
	st.rangeAdd(1, 0, st.n-1, l, r, delta)
}

func (st *LazySegmentTree) rangeAdd(node, lo, hi, l, r, delta int) {
	st.push(node, lo, hi)
	if r < lo || hi < l {
		return
	}
	if l <= lo && hi <= r {
		st.lazy[node] += delta // NOT BIRAK, aşağı inme
		st.push(node, lo, hi)
		return
	}
	mid := (lo + hi) / 2
	st.rangeAdd(2*node, lo, mid, l, r, delta)
	st.rangeAdd(2*node+1, mid+1, hi, l, r, delta)
	st.tree[node] = st.tree[2*node] + st.tree[2*node+1]
}

func (st *LazySegmentTree) Query(l, r int) int {
	if st.n == 0 || l > r {
		return 0
	}
	return st.query(1, 0, st.n-1, l, r)
}

func (st *LazySegmentTree) query(node, lo, hi, l, r int) int {
	st.push(node, lo, hi) // okumadan önce notu uygula
	if r < lo || hi < l {
		return 0
	}
	if l <= lo && hi <= r {
		return st.tree[node]
	}
	mid := (lo + hi) / 2
	return st.query(2*node, lo, mid, l, r) + st.query(2*node+1, mid+1, hi, l, r)
}

func main() {
	data := []int{1, 2, 3, 4, 5, 6, 7, 8}
	st := NewLazy(data)

	fmt.Println("dizi:", data)
	fmt.Println("toplam[0..7] =", st.Query(0, 7))
	fmt.Println()

	st.RangeAdd(1, 6, 5) // 1..6 arasındaki 6 elemana +5
	fmt.Println("[1..6] aralığına +5 eklendi")
	fmt.Println("toplam[0..7] =", st.Query(0, 7), "(önceki 36 + 6×5 = 66)")
	fmt.Println("toplam[1..6] =", st.Query(1, 6))
	fmt.Println("toplam[0..0] =", st.Query(0, 0), "← etkilenmedi")
	fmt.Println("toplam[7..7] =", st.Query(7, 7), "← etkilenmedi")

	fmt.Println()
	st.RangeAdd(0, 3, 10)
	fmt.Println("[0..3] aralığına +10 eklendi")
	for i := range 8 {
		fmt.Printf("  eleman[%d] = %d\n", i, st.Query(i, i))
	}
	fmt.Println("toplam[0..7] =", st.Query(0, 7))
}

package main

import "fmt"

type Fenwick struct {
	tree []int // 1 tabanlı
	n    int
}

func NewFenwick(n int) *Fenwick {
	return &Fenwick{tree: make([]int, n+1), n: n}
}

func FromSlice(data []int) *Fenwick {
	f := NewFenwick(len(data))
	for i, v := range data {
		f.Add(i, v)
	}
	return f
}

// Add: i. elemana delta ekler — O(log n)
func (f *Fenwick) Add(i, delta int) {
	for i++; i <= f.n; i += i & -i { // en düşük biti ekleyerek ilerle
		f.tree[i] += delta
	}
}

// PrefixSum: [0, i] toplamı — O(log n)
func (f *Fenwick) PrefixSum(i int) int {
	sum := 0
	for i++; i > 0; i -= i & -i { // en düşük biti çıkararak geri git
		sum += f.tree[i]
	}
	return sum
}

// RangeSum: [l, r] kapalı aralığı — O(log n)
func (f *Fenwick) RangeSum(l, r int) int {
	if l > r {
		return 0
	}
	if l == 0 {
		return f.PrefixSum(r)
	}
	return f.PrefixSum(r) - f.PrefixSum(l-1)
}

func main() {
	data := []int{3, 1, 4, 1, 5, 9, 2, 6}
	f := FromSlice(data)

	fmt.Println("dizi:", data)
	fmt.Println("iç dizi (1 tabanlı):", f.tree[1:])
	fmt.Println()

	fmt.Println("önek toplamları:")
	for i := range data {
		fmt.Printf("  [0..%d] = %d\n", i, f.PrefixSum(i))
	}

	fmt.Println()
	for _, r := range [][2]int{{0, 7}, {2, 5}, {5, 5}, {3, 6}} {
		fmt.Printf("toplam[%d..%d] = %d\n", r[0], r[1], f.RangeSum(r[0], r[1]))
	}

	fmt.Println()
	f.Add(2, 6) // indeks 2'ye +6 (4 → 10)
	fmt.Println("indeks 2'ye +6 eklendi")
	fmt.Println("toplam[0..7] =", f.RangeSum(0, 7))
	fmt.Println("toplam[2..5] =", f.RangeSum(2, 5))

	// En düşük bit hilesi
	fmt.Println()
	fmt.Println("i & -i değerleri:")
	for i := 1; i <= 8; i++ {
		fmt.Printf("  %d (%04b) → %d\n", i, i, i&-i)
	}
}