Advanced structures: name the node's meaning

• Trie: a path represents a prefix; a flag marks a stored word.
• Fenwick: each cell stores a particular interval sum.
• Reconstruct an operation from those meanings before coding.

Trie: path versus terminal flag

After Insert("cart"):

• Search("car") = false
• StartsWith("car") = true
• Search("cart") = true

Insert("car") marks an existing node terminal and preserves its child t. Duplicate insertion leaves membership unchanged.

Fenwick cell invariant

External nums is zero-based; internal a is one-based.

bit[i] = sum(a[i-lowbit(i)+1 .. i]), where lowbit(i)=i&-i.

For [3,1,4,1,5,9,2,6]:

bit[1..8] = [3,4,4,9,5,14,2,31].

bit[6]=a[5]+a[6]=14, not the first-six sum 23.

Query: subtract lowbit

F(k) sums the first k external elements; F(0)=0.

F(7) visits 7 → 6 → 4 → 0:

• [7,7] contributes 2.
• [5,6] contributes 14.
• [1,4] contributes 9.

Disjoint intervals cover the prefix; answer 25.

Inclusive external range

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

For [2,6]: F(7)-F(2)=25-4=21.

For [0,0]: F(1)-F(0)=3.

The extra one is determined by F's element-count convention.

Assignment: propagate a delta upward

Update(5,2) replaces old value 9, so delta is -7.

• Start at internal index 6.
• Cell 6: 14 → 7.
• Cell 8: 31 → 24.
• Next index 16 exceeds n=8; stop.

Save old[5]=2. Repeating the assignment now has delta zero.

After the update

F(7) still visits 7,6,4: 2+7+9=18.

Range [2,6] is 18-4=14.

A query subtracts lowbit; an update adds lowbit. Starting an update at index zero would never advance.

Costs and checks

• Trie operations: O(L) for a fixed alphabet; listing completions costs extra.
• Fenwick build: O(n log n) with repeated adds; memory O(n).
• Fenwick assignment and range sum: O(log n).
• Check negative values, repeated assignments, both endpoints, and large sums.