Segment-Tree
Segment Tree and Fenwick Tree
·3 mins
Algorithm
Segment-Tree
Binary-Indexed-Tree
Design
Point updates with range queries: a Fenwick tree (binary indexed tree) jumps by i & -i, and a segment tree recursively halves the range; both take O(log n) per operation
LeetCode 307: Range Sum Query - Mutable
·3 mins
LeetCode
Medium
Segment-Tree
Binary-Indexed-Tree
Design
Array
LeetCode 307 note: point updates with range sums make prefix sums O(n) per update; a segment tree or Fenwick tree makes both operations O(log n)
LeetCode 3719: Longest Balanced Subarray I
·2 mins
LeetCode
Medium
Hash-Table
Prefix-Sum
Segment-Tree
Array
LeetCode 3719 note: n is only 1500, so fix the left end and extend right, maintaining distinct odds and evens in two sets