Skip to content

[pull] master from halfrost:master #49

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
pull merged 1 commit into from
Jun 29, 2026
Merged

[pull] master from halfrost:master #49

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Binary file added ctl/ctl
View file
Open in desktop
Binary file not shown.
20 changes: 8 additions & 12 deletions template/SegmentTree.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -81,10 +81,10 @@ func (st *SegmentTree) queryLazyInTree(treeIndex, left, right, queryLeft, queryR
return 0 // represents a null node
}
if st.lazy[treeIndex] != 0 { // this node is lazy
for i := 0; i < right-left+1; i++ {
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
// st.tree[treeIndex] += (right - left + 1) * st.lazy[treeIndex] // normalize current node by removing lazinesss
}
// merge 为幂等操作（如 max/min）时，对整段套用一次即等价于对每个元素套用，
// 故 O(1) 下推即可；按区间长度循环会把下推退化成 O(区间)，失去 lazy 的意义。
// 若改用「区间求和 + 区间加」语义，这里应换成 st.tree[treeIndex] += (right-left+1) * st.lazy[treeIndex]。
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
if left != right { // update lazy[] for children nodes
st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], st.lazy[treeIndex])
st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], st.lazy[treeIndex])
Expand Down Expand Up @@ -145,10 +145,8 @@ func (st *SegmentTree) UpdateLazy(updateLeft, updateRight, val int) {
func (st *SegmentTree) updateLazyInTree(treeIndex, left, right, updateLeft, updateRight, val int) {
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.leftChild(treeIndex), st.rightChild(treeIndex)
if st.lazy[treeIndex] != 0 { // this node is lazy
for i := 0; i < right-left+1; i++ {
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
//st.tree[treeIndex] += (right - left + 1) * st.lazy[treeIndex] // normalize current node by removing laziness
}
// 幂等 merge（如 max/min）整段套用一次即可，O(1) 下推（求和语义则用 (right-left+1)*lazy）。
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
if left != right { // update lazy[] for children nodes
st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], st.lazy[treeIndex])
st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], st.lazy[treeIndex])
Expand All @@ -163,10 +161,8 @@ func (st *SegmentTree) updateLazyInTree(treeIndex, left, right, updateLeft, upda
}

if updateLeft <= left && right <= updateRight { // segment is fully within update range
for i := 0; i < right-left+1; i++ {
st.tree[treeIndex] = st.merge(st.tree[treeIndex], val)
//st.tree[treeIndex] += (right - left + 1) * val // update segment
}
// 同理，幂等 merge 整段套用一次即可（求和语义则用 (right-left+1)*val）。
st.tree[treeIndex] = st.merge(st.tree[treeIndex], val)
if left != right { // update lazy[] for children
st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], val)
st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], val)
Expand Down
99 changes: 99 additions & 0 deletions template/SegmentTree_test.go
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,99 @@
package template

import "testing"

func sum(i, j int) int { return i + j }
func maxv(i, j int) int {
if i > j {
return i
}
return j
}

// 单点更新 + 区间查询（求和语义）
func Test_SegmentTree_PointUpdate(t *testing.T) {
st := SegmentTree{}
st.Init([]int{1, 3, 5, 7, 9, 11}, sum)

checks := []struct {
l, r, want int
}{
{0, 5, 36},
{1, 3, 15},
{2, 2, 5},
{0, 0, 1},
}
for _, c := range checks {
if got := st.Query(c.l, c.r); got != c.want {
t.Fatalf("Query(%d,%d) = %d, want %d", c.l, c.r, got, c.want)
}
}

st.Update(2, 6) // nums[2]: 5 -> 6
if got := st.Query(1, 3); got != 16 {
t.Fatalf("after Update, Query(1,3) = %d, want 16", got)
}
if got := st.Query(0, 5); got != 37 {
t.Fatalf("after Update, Query(0,5) = %d, want 37", got)
}
}

// 区间更新 + 区间查询（max 幂等语义，等价于 Falling Squares / Skyline 的用法）
// 这是本次把 lazy 下推从 O(区间) 改成 O(1) 单次 merge 所影响的路径。
func Test_SegmentTree_Lazy_Max(t *testing.T) {
st := SegmentTree{}
st.Init([]int{0, 0, 0, 0, 0}, maxv)

st.UpdateLazy(0, 2, 5) // [5,5,5,0,0]
if got := st.QueryLazy(0, 4); got != 5 {
t.Fatalf("QueryLazy(0,4) = %d, want 5", got)
}
if got := st.QueryLazy(3, 4); got != 0 {
t.Fatalf("QueryLazy(3,4) = %d, want 0", got)
}
if got := st.QueryLazy(1, 2); got != 5 {
t.Fatalf("QueryLazy(1,2) = %d, want 5", got)
}

st.UpdateLazy(2, 4, 3) // max into [2,4]: [5,5,5,3,3]
cases := []struct {
l, r, want int
}{
{0, 4, 5},
{3, 4, 3},
{2, 2, 5},
{4, 4, 3},
{0, 0, 5},
}
for _, c := range cases {
if got := st.QueryLazy(c.l, c.r); got != c.want {
t.Fatalf("QueryLazy(%d,%d) = %d, want %d", c.l, c.r, got, c.want)
}
}
}

// 计数线段树：按值域区间统计已插入元素个数（327/493/315/1649 的用法）
func Test_SegmentCountTree(t *testing.T) {
st := SegmentCountTree{}
st.Init([]int{1, 2, 3, 4, 5}, sum) // 有序去重的值域

for _, v := range []int{3, 3, 5, 1} { // 插入 3,3,5,1
st.UpdateCount(v)
}

cases := []struct {
lo, hi, want int // 统计值在 [lo,hi] 的个数
}{
{1, 5, 4},
{3, 3, 2},
{3, 5, 3},
{1, 2, 1},
{4, 5, 1},
{2, 2, 0},
}
for _, c := range cases {
if got := st.Query(c.lo, c.hi); got != c.want {
t.Fatalf("Query(%d,%d) = %d, want %d", c.lo, c.hi, got, c.want)
}
}
}
21 changes: 9 additions & 12 deletions website/content.en/ChapterThree/Segment_Tree.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -208,10 +208,9 @@ func (st *SegmentTree) queryLazyInTree(treeIndex, left, right, queryLeft, queryR
return 0 // represents a null node
}
if st.lazy[treeIndex] != 0 { // this node is lazy
for i := 0; i < right-left+1; i++ {
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
// st.tree[treeIndex] += (right - left + 1) * st.lazy[treeIndex] // normalize current node by removing lazinesss
}
// 幂等 merge（如 max/min）整段套用一次即可，O(1) 下推；
// 按区间长度循环会退化成 O(区间)。求和语义则改成 (right-left+1)*st.lazy[treeIndex]。
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
if left != right { // update lazy[] for children nodes
st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], st.lazy[treeIndex])
st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], st.lazy[treeIndex])
Expand Down Expand Up @@ -310,10 +309,9 @@ func (st *SegmentTree) UpdateLazy(updateLeft, updateRight, val int) {
func (st *SegmentTree) updateLazyInTree(treeIndex, left, right, updateLeft, updateRight, val int) {
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.leftChild(treeIndex), st.rightChild(treeIndex)
if st.lazy[treeIndex] != 0 { // this node is lazy
for i := 0; i < right-left+1; i++ {
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
//st.tree[treeIndex] += (right - left + 1) * st.lazy[treeIndex] // normalize current node by removing laziness
}
// 幂等 merge（如 max/min）整段套用一次即可，O(1) 下推；
// 按区间长度循环会退化成 O(区间)。求和语义则改成 (right-left+1)*st.lazy[treeIndex]。
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
if left != right { // update lazy[] for children nodes
st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], st.lazy[treeIndex])
st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], st.lazy[treeIndex])
Expand All @@ -328,10 +326,9 @@ func (st *SegmentTree) updateLazyInTree(treeIndex, left, right, updateLeft, upda
}

if updateLeft <= left && right <= updateRight { // segment is fully within update range
for i := 0; i < right-left+1; i++ {
st.tree[treeIndex] = st.merge(st.tree[treeIndex], val)
//st.tree[treeIndex] += (right - left + 1) * val // update segment
}
// 幂等 merge（如 max/min）整段套用一次即可，O(1) 下推；
// 按区间长度循环会退化成 O(区间)。求和语义则改成 (right-left+1)*val。
st.tree[treeIndex] = st.merge(st.tree[treeIndex], val)
if left != right { // update lazy[] for children
st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], val)
st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], val)
Expand Down
21 changes: 9 additions & 12 deletions website/content/ChapterThree/Segment_Tree.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -208,10 +208,9 @@ func (st *SegmentTree) queryLazyInTree(treeIndex, left, right, queryLeft, queryR
return 0 // represents a null node
}
if st.lazy[treeIndex] != 0 { // this node is lazy
for i := 0; i < right-left+1; i++ {
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
// st.tree[treeIndex] += (right - left + 1) * st.lazy[treeIndex] // normalize current node by removing lazinesss
}
// 幂等 merge（如 max/min）整段套用一次即可，O(1) 下推；
// 按区间长度循环会退化成 O(区间)。求和语义则改成 (right-left+1)*st.lazy[treeIndex]。
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
if left != right { // update lazy[] for children nodes
st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], st.lazy[treeIndex])
st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], st.lazy[treeIndex])
Expand Down Expand Up @@ -310,10 +309,9 @@ func (st *SegmentTree) UpdateLazy(updateLeft, updateRight, val int) {
func (st *SegmentTree) updateLazyInTree(treeIndex, left, right, updateLeft, updateRight, val int) {
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.leftChild(treeIndex), st.rightChild(treeIndex)
if st.lazy[treeIndex] != 0 { // this node is lazy
for i := 0; i < right-left+1; i++ {
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
//st.tree[treeIndex] += (right - left + 1) * st.lazy[treeIndex] // normalize current node by removing laziness
}
// 幂等 merge（如 max/min）整段套用一次即可，O(1) 下推；
// 按区间长度循环会退化成 O(区间)。求和语义则改成 (right-left+1)*st.lazy[treeIndex]。
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
if left != right { // update lazy[] for children nodes
st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], st.lazy[treeIndex])
st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], st.lazy[treeIndex])
Expand All @@ -328,10 +326,9 @@ func (st *SegmentTree) updateLazyInTree(treeIndex, left, right, updateLeft, upda
}

if updateLeft <= left && right <= updateRight { // segment is fully within update range
for i := 0; i < right-left+1; i++ {
st.tree[treeIndex] = st.merge(st.tree[treeIndex], val)
//st.tree[treeIndex] += (right - left + 1) * val // update segment
}
// 幂等 merge（如 max/min）整段套用一次即可，O(1) 下推；
// 按区间长度循环会退化成 O(区间)。求和语义则改成 (right-left+1)*val。
st.tree[treeIndex] = st.merge(st.tree[treeIndex], val)
if left != right { // update lazy[] for children
st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], val)
st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], val)
Expand Down
9 changes: 9 additions & 0 deletions website/themes/book/assets/search.js
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -27,6 +27,15 @@
// Don't hijack typing in other editable fields (e.g. the Gitalk comment box).
// Otherwise a search hotkey ("s" / "/") typed there steals focus to the search
// box, making it lose focus after every keystroke.
//
// Prefer event.target (the element that actually received the key) over
// document.activeElement — it is more reliable across frameworks/nesting.
// Bail out for any editable element or anything inside the Gitalk widget.
const target = event.target;
if (target && typeof target.closest === 'function' &&
target.closest('input, textarea, select, [contenteditable=""], [contenteditable="true"], #gitalk-container, .gt-container')) {
return;
}
const active = document.activeElement;
if (active && (active.tagName === 'INPUT' || active.tagName === 'TEXTAREA' || active.tagName === 'SELECT' || active.isContentEditable)) {
return;
Expand Down
Loading