Advanced Data Structures

Choose what each node means

This module assumes arrays, maps, prefix sums, and binary representation. You will build a trie for word/prefix queries and a Fenwick tree for assignments and range sums. Before coding, be able to state what a node represents, which nodes an operation touches, and why the untouched nodes remain valid.

A set answers whole-word membership directly. A trie also shares the traversal for words beginning with the same prefix. A static prefix-sum array answers ranges quickly, but one assignment changes every later prefix; a Fenwick tree stores carefully chosen partial sums to make both operations logarithmic.

Trie: an existing path is not necessarily a word

A node has a collection of child edges and an isWord flag. The root represents the empty prefix. Following edges c → a → r represents the prefix car. The exercise uses nonempty lowercase a-z strings, so byte traversal in Go and character traversal in Python refer to the same alphabet.

Insert cart, then cat, then car:

Operation	New path portion	Terminal flags after operation
Insert cart	root → c → a → r → t	only cart is terminal
Insert cat	reuse c,a; add t under a	cart, cat
Insert car	reuse the full existing path	cart, cat, car
Insert car again	none	unchanged

After the first insertion, Search("car") is false and StartsWith("car") is true. After the third, both are true. Marking the car node terminal must not remove its t child: Search("cart") stays true. A terminal node can also have children. Inserting a duplicate has no additional effect on membership.

All three operations traverse the requested characters. Insert creates only missing edges and sets the final flag. Search fails on a missing edge and, after the last character, returns the flag. StartsWith fails on a missing edge but otherwise succeeds, without requiring a terminal flag. Querying cap after all the insertions fails at the missing p edge; sharing ca is not enough.

For length L, each operation takes O(L) with constant-time child access for this fixed alphabet. Storage is O(total inserted characters) in the worst case; shared prefixes can reduce the node count. Maps allocate children on demand; 26-entry arrays trade sparse memory overhead for direct indexing. A trie does not automatically use less memory than a set, and enumerating autocomplete results costs additional work proportional to the visited output subtree. The Princeton trie treatment provides further examples of prefix traversal and string-symbol-table operations.

Fenwick: define the stored interval first

Keep the external array zero-based. Internally, call its values a[1..n], where a[i] = nums[i-1]. Index zero in the tree is unused. Define:

lowbit(i) = i & -i                         for i > 0
bit[i] = sum of a[i-lowbit(i)+1 .. i]       inclusive

The lowest set bit is the size of the interval ending at i. For example, 6 is binary 110, so lowbit(6)=2 and bit[6] stores a[5]+a[6].

Take nums=[3,1,4,1,5,9,2,6]:

Internal i	lowbit(i)	Internal interval stored	bit[i]
1	1	[1,1]	3
2	2	[1,2]	4
3	1	[3,3]	4
4	4	[1,4]	9
5	1	[5,5]	5
6	2	[5,6]	14
7	1	[7,7]	2
8	8	[1,8]	31

Do not treat bit as a plain prefix-sum array: bit[6]=14, while the sum of the first six external values is 23.

Query downward through disjoint intervals

Let F(k) mean the sum of the first k external elements: nums[0:k]. This count-based convention makes F(0)=0. Start the internal walk at i=k, add bit[i], then set i=i-lowbit(i) until it reaches zero.

For F(7):

Visit	Interval added	Running sum	Next i
7	[7,7] = 2	2	6
6	[5,6] = 14	16	4
4	[1,4] = 9	25	0

After adding an interval ending at i, subtracting its length lands immediately before its start. The intervals partition 1..k: no gap and no double count. Subtracting lowbit clears a set bit, so the walk uses O(log n) steps.

An inclusive external range [left,right] is:

SumRange(left,right) = F(right+1) - F(left)

For [2,6], this is F(7)-F(2)=25-4=21. For [0,0], it is F(1)-F(0)=3. Using F(right) would drop the right endpoint; using F(left+1) would drop the left endpoint. An inclusive-index prefix API would use a different formula; write down the convention before translating indices.

Assign upward through the containing intervals

The public operation Update(index,val) is assignment, not addition. Keep a private copy of the current values to calculate delta=val-old[index]. At internal i=index+1, add delta to bit[i], then move to i+lowbit(i) while i<=n. Those are exactly the stored intervals containing the changed position. Each jump reaches the next containing interval; its lowbit grows, so there are O(log n) updates. Starting at zero would never advance.

Assign external index 5 from 9 to 2. Delta is -7 and internal start is 6:

Tree cell changed	Its interval	Before	After	Next i
6	[5,6]	14	7	8
8	[1,8]	31	24	16, stop

The other six cells are unchanged. Store old[5]=2 too. Now F(7) traverses the same cells 7,6,4, but totals 2+7+9=18, and range [2,6] is 18-4=14. Assigning index 5 to 2 again propagates delta zero. Adding val directly would increase the sum on that repeated assignment and violate the interface.

Initialize a zero tree and add each input value along its containing intervals: that construction costs O(n log n), with O(n) storage. Updates and queries each cost O(log n). An O(n) constructor is possible but is not required here. With up to 10^5 values of magnitude 10^5, sums can have magnitude 10^10; the exercise's Go API assumes 64-bit int, and Python integers represent this range directly. A 32-bit port needs a wider sum type and return signature.

Complete a trace, then work independently

For the fresh array [2,5,1,4], the internal tree is [2,7,1,12] at cells 1 through 4. Assign external index 2 to -3. Fill in the missing consequences:

Decision	Given work	Your missing result
Compute the change	old value 1; new value -3	delta ?
Find containing cells	start internal 3; then 4	new bit[3] and bit[4] ?
Query F(3)	add cells 3 and 2	sum ?
Query external [1,3]	F(4)-F(1)	sum ?

Check the partial trace after attempting it

Delta is -4; bit[3] becomes -3 and bit[4] becomes 8. F(3) is -3+7=4, and range [1,3] is 8-2=6. The tree now stores [2,7,-3,8].

Continue from that state, but cover the table: assign external index 1 to 0, then assign it to 0 again. List the cells visited on each update and compute the whole-array sum. Explain why the second operation changes nothing.

Check the independent continuation

The first delta is 0-5=-5, touching cells 2 and 4. The tree becomes [2,2,-3,3], and the whole-array sum is 3. Saving the new current value makes the repeated assignment's delta zero; it visits the same cells without changing them. The explicit array is [2,0,-3,4].

For the trie, insert rain, raindrop, and ran. Before running code, name which of ra, rain, and ran are terminal and which have children. Then construct your own query that fails on a missing edge despite sharing a prefix. A later revisit should use different words and array values, with the worked state tables closed.

Reconstruct, then check

1. Implement Trie Prefix Search. After inserting stone, predict searches for sto, stone, and stork. Insert sto and verify that the longer word remains searchable.
2. Before Fenwick Range Sum, redraw the interval table for four values. Work one negative assignment and one repeated assignment on paper, then compare every range with a direct sum.
3. If your range is off by one, revisit F's count convention. If the first assignment works but the second fails, inspect the saved old value. If trie prefixes become stored words, inspect where terminal flags are set.