Advanced Data Structures

1 / 4

Trie

  • Each node stores children + isWord
  • Insert/Search/StartsWith in O(L)
  • Great for prefix queries
2 / 4

Fenwick Tree

  • Point update in O(log n)
  • Prefix sum in O(log n)
  • Range sum = prefix(r) - prefix(l-1)
  • Internally 1-indexed
3 / 4

Takeaway

  • Trie: structure over strings
  • Fenwick: structure over indices
4 / 4
Use arrow keys or click edges to navigate. Press H to toggle help, F for fullscreen.