Cấu trúc cây nâng caoAdvanced Tree Structures

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

The trees covered so far are all about ordering: a binary search tree keeps keys sorted so you can find one in O(log n), and a balanced tree (AVL, red-black, B-tree — see ./11-balanced-and-multiway-trees.md) keeps that guarantee under insertion. The structures in this note are different. They are trees built to answer questions that a sorted container simply cannot answer efficiently:

• Tries answer “which stored keys start with this prefix?” — a question a hash table cannot answer at all and a BST answers awkwardly. The key insight is that the path from the root spells the key, so no node needs to store the key itself.
• Segment trees answer “what is the sum/min/max/gcd over a..b?” while the underlying array is still being modified — recursive halving turns a range into O(log n) precomputed pieces.
• Fenwick trees (Binary Indexed Trees) answer the prefix-sum version of that question with a quarter of the memory and about a third of the code, by exploiting the binary representation of the index.
• Suffix arrays and suffix trees answer “does this pattern occur in this text, and where?” for a text you will search many times — by preprocessing every suffix once.

The common theme is precomputation with a trade-off. Each structure spends memory and build time up front to convert an O(n) scan into an O(log n) or O(1) lookup. Choosing between them is mostly about which operations you need and, crucially, whether the data changes: a static array of prefix sums beats every structure here for read-only prefix queries, and knowing that saves you from building a segment tree you did not need.

Fundamentals

Tries (prefix trees)

A trie — from retrieval, usually pronounced “try” to distinguish it from “tree” — is a search tree for string keys where no node stores a key. Instead, a node’s position in the tree defines the string it represents: the concatenation of the edge labels from the root. All descendants of a node share that node’s string as a prefix, and the root represents the empty string.

Trie holding {"car", "cart", "cat", "do", "dog"}

               (root)
              /      \
            c          d
            |          |
            a          o*
           / \         |
         r*   t*       g*
         |
         t*

* = a stored word ends here

"ca" is a valid prefix (the node exists) but not a stored word (no *)

That structure is what makes prefix queries trivial: to find every word starting with "ca", walk two edges and enumerate the subtree. A hash table cannot do this — hashing destroys the relationship between "car" and "cart" — and a sorted array can (binary search for the prefix range) but cannot then support cheap insertion.

class TrieNode:
    __slots__ = ("children", "is_word")

    def __init__(self):
        self.children = {}      # character -> TrieNode
        self.is_word = False    # True if a stored key ends exactly here


class Trie:
    """Prefix tree over strings. All operations are O(L) in the key length L,
    independent of how many keys are stored."""

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            # setdefault creates the child only if this character is new
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

    def _walk(self, prefix):
        """Return the node reached by spelling out prefix, or None if it dead-ends."""
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        """Is word a stored key? Reaching the node is not enough — it must be marked."""
        node = self._walk(word)
        return node is not None and node.is_word

    def starts_with(self, prefix):
        """Is any stored key prefixed by this string?"""
        return self._walk(prefix) is not None

    def autocomplete(self, prefix, limit=10):
        """Up to `limit` stored keys with the given prefix, in lexicographic order."""
        node = self._walk(prefix)
        results = []
        if node is None:
            return results
        stack = [(node, prefix)]                  # explicit stack instead of recursion
        while stack and len(results) < limit:
            cur, word = stack.pop()
            if cur.is_word:
                results.append(word)
            # push in reverse so the smallest character is popped first
            for ch in sorted(cur.children, reverse=True):
                stack.append((cur.children[ch], word + ch))
        return results


t = Trie()
for w in ["car", "cart", "cat", "do", "dog", "dodge"]:
    t.insert(w)

print(t.search("car"), t.search("ca"))     # True False
print(t.starts_with("ca"))                 # True
print(t.autocomplete("ca"))                # ['car', 'cart', 'cat']
print(t.autocomplete("do"))                # ['do', 'dodge', 'dog']

Deletion needs care: unmarking is_word is not enough, because the now-unused nodes leak memory and slow down traversals. You have to prune back up the path, stopping as soon as you hit a node that has other children or ends another word.

def delete(self, word):
    """Remove word if present, pruning nodes that become useless. O(L)."""
    path = [self.root]
    node = self.root
    for ch in word:
        node = node.children.get(ch)
        if node is None:
            return False                       # word was never stored
        path.append(node)
    if not node.is_word:
        return False
    node.is_word = False
    for i in range(len(word) - 1, -1, -1):     # walk back towards the root
        child, parent = path[i + 1], path[i]
        if child.children or child.is_word:
            break                              # still needed by another key
        del parent.children[word[i]]
    return True


Trie.delete = delete

Complexity. Let L be the key length, n the number of keys, Σ the alphabet size, and N the total number of characters stored.

Note what is not in that table: n never appears. A trie’s lookup cost depends only on the length of the key you are looking up. A hash table also gives O(L) for string keys (you must hash the whole string), so the trie’s real advantage is not raw lookup speed — it is prefix enumeration, ordered iteration, and the absence of collisions or resizing.

The memory cost of a trie — the honest version

Tries are memory-hungry, and this is the single most common reason to reject one in production.

The child pointer representation is the whole story:

In CPython, the TrieNode above costs roughly 56 bytes for the object plus at least 64 bytes for the dict, so a trie over 100k English words (about 900k characters, maybe 250k distinct nodes after prefix sharing) lands in the tens of megabytes — for data that fits in under 1 MB as a plain list of strings. If you only need membership testing, a set of strings is smaller, faster, and one line of code. Build a trie when prefix structure is the point, not as a general-purpose string container.

Compressed tries (radix tries / PATRICIA)

Most of that memory goes to chains of single-child nodes — the "dodg" in "dodge" is four nodes doing no branching. A compressed trie, also called a radix trie or PATRICIA trie, collapses each such chain into a single edge labelled with the whole substring:

plain trie for {"romane", "romanus", "rubens"}     radix trie for the same

  r                                                       r
  |                                                      / \
  o - m - a - n - e*                              "om" /   \ "ubens"*
  |               \                                   /     \
  u - b - e - n - s*   (and: n - u - s*)          "an"       o
                                                  /  \
                                             "e"*     "us"*

The number of nodes drops from O(N) (total characters) to O(n) (number of keys) — a radix trie with n keys has at most n leaves and n−1 internal branching nodes, regardless of how long the keys are. Lookup is still O(L) but with far fewer pointer dereferences and much better cache behaviour, at the cost of substring comparison logic and node-splitting on insert.

This is not an academic curiosity. Radix tries are what real systems use: the Linux kernel’s page cache and IP routing tables, etcd’s and Redis’s key storage (Redis’s rax), Go’s net/http routers, and Ethereum’s Merkle Patricia trie all use this shape. A related variant, the ternary search trie, stores three children per node (<, =, >) and is a good middle ground between an array-of-Σ trie and a BST.

Key Concepts

Segment trees

A segment tree answers range queries over a mutable array. Given data[0..n−1] and an associative operation (sum, min, max, gcd, “count of zeros”, almost anything), it supports:

• query(l, r) — the operation folded over data[l..r], in O(log n)
• update(i, v) — set data[i] = v, in O(log n)

Neither is impressive alone. A plain array does update in O(1) and query in O(n); a prefix-sum array does query in O(1) and update in O(n). The segment tree’s contribution is making both logarithmic, which is what you need when reads and writes interleave.

The idea is recursive halving. The root covers [0, n−1]; each internal node splits its range in half and stores the operation applied to its two children; the leaves are the individual elements.

data = [1, 3, 5, 7, 9, 11]        (sums shown in each node)

                   [0..5] 36
                  /          \
          [0..2] 9            [3..5] 27
          /      \            /       \
    [0..1] 4   [2..2] 5   [3..4] 16  [5..5] 11
    /     \                /     \
[0] 1   [1] 3          [3] 7   [4] 9

query(1, 3) = 3 + 5 + 7 = 15
  → [1..1] fully inside → 3
  → [2..2] fully inside → 5
  → [3..3] fully inside → 7

Any range [l, r] decomposes into at most 2 log n fully-covered nodes, because at each level the query boundary can only “cut” two nodes (one at each end). That is the entire complexity argument.

class SegmentTree:
    """Range-sum segment tree with point update over a fixed-size array.

    Stored in a flat array: node 1 is the root; the children of node v are
    2v and 2v+1. Size 4n is a safe upper bound for any n.
    """

    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        if self.n:
            self._build(data, 1, 0, self.n - 1)

    def _build(self, data, v, lo, hi):
        if lo == hi:                          # leaf: holds one element
            self.tree[v] = data[lo]
            return
        mid = (lo + hi) // 2
        self._build(data, 2 * v, lo, mid)
        self._build(data, 2 * v + 1, mid + 1, hi)
        self.tree[v] = self.tree[2 * v] + self.tree[2 * v + 1]

    def update(self, idx, value):
        """data[idx] = value, in O(log n) — one root-to-leaf path is rewritten."""
        self._update(1, 0, self.n - 1, idx, value)

    def _update(self, v, lo, hi, idx, value):
        if lo == hi:
            self.tree[v] = value
            return
        mid = (lo + hi) // 2
        if idx <= mid:
            self._update(2 * v, lo, mid, idx, value)
        else:
            self._update(2 * v + 1, mid + 1, hi, idx, value)
        self.tree[v] = self.tree[2 * v] + self.tree[2 * v + 1]

    def query(self, left, right):
        """Sum of data[left..right], inclusive, in O(log n)."""
        return self._query(1, 0, self.n - 1, left, right)

    def _query(self, v, lo, hi, left, right):
        if right < lo or hi < left:           # disjoint: contributes the identity
            return 0
        if left <= lo and hi <= right:        # fully covered: use the stored value
            return self.tree[v]
        mid = (lo + hi) // 2                  # partial: recurse into both halves
        return (self._query(2 * v, lo, mid, left, right)
                + self._query(2 * v + 1, mid + 1, hi, left, right))


st = SegmentTree([1, 3, 5, 7, 9, 11])
print(st.query(1, 3))      # 15
st.update(1, 10)
print(st.query(1, 3))      # 22

To change the operation, change three things: the combine step (+), the identity returned for disjoint nodes (0 for sum, float('inf') for min, -inf for max, 0 for gcd), and the leaf initialization. Everything else is untouched — segment trees are generic over any monoid (an associative operation with an identity element). This is the property to check before reaching for one: “sum” works, “min” works, “the k-th largest in the range” does not, because you cannot combine two children’s answers into the parent’s.

Complexity: build O(n), query O(log n), point update O(log n), space O(4n). The 4n is a convenient over-allocation for the recursive layout; an iterative bottom-up implementation over a padded power-of-two array needs only 2n and is meaningfully faster, at the cost of being harder to extend with lazy propagation.

Lazy propagation

Point updates are the easy case. What if you need to add 5 to every element in data[l..r]? Doing it element by element is O(r − l), which throws away the whole point of the structure.

Lazy propagation fixes this: when an update fully covers a node’s range, apply it to that node’s aggregate and record a “pending” marker in a parallel lazy[] array — do not descend. Push the marker down to the children only when a later query or update actually needs to look inside that node. Each operation still touches O(log n) nodes.

class LazySegmentTree:
    """Range-add, range-sum segment tree. Both operations O(log n).

    lazy[v] is an update already reflected in tree[v] but not yet in v's
    children; it is pushed down only when we must descend past v.
    """

    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)
        self.lazy = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, v, lo, hi):
        if lo == hi:
            self.tree[v] = data[lo]
            return
        mid = (lo + hi) // 2
        self._build(data, 2 * v, lo, mid)
        self._build(data, 2 * v + 1, mid + 1, hi)
        self.tree[v] = self.tree[2 * v] + self.tree[2 * v + 1]

    def _apply(self, v, lo, hi, delta):
        self.tree[v] += delta * (hi - lo + 1)   # every element in the range grew by delta
        self.lazy[v] += delta

    def _push(self, v, lo, hi):
        if self.lazy[v]:
            mid = (lo + hi) // 2
            self._apply(2 * v, lo, mid, self.lazy[v])
            self._apply(2 * v + 1, mid + 1, hi, self.lazy[v])
            self.lazy[v] = 0

    def add(self, left, right, delta, v=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if right < lo or hi < left:
            return
        if left <= lo and hi <= right:          # fully covered: stop here, mark lazily
            self._apply(v, lo, hi, delta)
            return
        self._push(v, lo, hi)
        mid = (lo + hi) // 2
        self.add(left, right, delta, 2 * v, lo, mid)
        self.add(left, right, delta, 2 * v + 1, mid + 1, hi)
        self.tree[v] = self.tree[2 * v] + self.tree[2 * v + 1]

    def query(self, left, right, v=1, lo=0, hi=None):
        if hi is None:
            hi = self.n - 1
        if right < lo or hi < left:
            return 0
        if left <= lo and hi <= right:
            return self.tree[v]
        self._push(v, lo, hi)                   # must descend, so settle the debt first
        mid = (lo + hi) // 2
        return (self.query(left, right, 2 * v, lo, mid)
                + self.query(left, right, 2 * v + 1, mid + 1, hi))


lst = LazySegmentTree([1, 3, 5, 7, 9, 11])
lst.add(1, 4, 10)            # add 10 to data[1..4]
print(lst.query(0, 5))       # 36 + 40 = 76
print(lst.query(2, 3))       # (5 + 10) + (7 + 10) = 32

Lazy propagation is where segment trees get genuinely tricky. Two rules save most of the pain: the lazy value must compose (two pending “add” updates combine into one; two pending “assign” updates keep the later one — and mixing add and assign requires an explicit composition rule and careful ordering), and _apply must know the range length for aggregate operations like sum. Get either wrong and the bugs are subtle and data-dependent.

Segment trees also generalize beyond arrays: persistent segment trees keep every historical version by path copying, merge-sort trees store a sorted list at each node for range-rank queries, and segment tree beats handles range-min-assignment. Those are worth knowing exist, not worth memorizing.

Fenwick trees / Binary Indexed Trees

A Fenwick tree (Peter Fenwick, 1994), or Binary Indexed Tree (BIT), does the most common segment-tree job — prefix sums with point updates — in a quarter of the memory and about fifteen lines of code. It works by reading the binary representation of the index.

The structure: use 1-based indexing, and let tree[i] store the sum of the i & -i elements ending at position i. The expression i & -i isolates the lowest set bit of i, because in two’s complement -i is ~i + 1, which flips every bit above the lowest set bit and leaves that bit intact.

i    binary   i & -i   tree[i] covers
1    0001       1      data[1..1]
2    0010       2      data[1..2]
3    0011       1      data[3..3]
4    0100       4      data[1..4]
5    0101       1      data[5..5]
6    0110       2      data[5..6]
7    0111       1      data[7..7]
8    1000       8      data[1..8]

prefix_sum(7) = tree[7] + tree[6] + tree[4]
              = data[7] + data[5..6] + data[1..4]
   index walk:  7 (0111) → 6 (0110) → 4 (0100) → 0     — strip the lowest set bit
   one node per set bit in 7, so at most log2(n) steps

add(5, delta) touches tree[5], tree[6], tree[8]
   index walk:  5 (0101) → 6 (0110) → 8 (1000) → past n — add the lowest set bit

Prefix sum strips bits (i -= i & -i); update adds them (i += i & -i). Each walk visits at most log₂ n indices, and the two walks are exact mirror images — which is the trick that makes the whole thing fit in fifteen lines.

class FenwickTree:
    """Binary Indexed Tree over positions 1..n.

    Point update and prefix sum, both O(log n). Space: n+1 integers.
    """

    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)      # index 0 is unused; the structure is 1-based

    def add(self, i, delta):
        """data[i] += delta, for 1 <= i <= n."""
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i                # jump to the next node whose range covers i

    def prefix_sum(self, i):
        """Sum of data[1..i]. prefix_sum(0) == 0."""
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i                # strip the lowest set bit
        return total

    def range_sum(self, left, right):
        """Sum of data[left..right], inclusive — subtraction is why sums work here."""
        return self.prefix_sum(right) - self.prefix_sum(left - 1)

    @classmethod
    def from_list(cls, data):
        """Build in O(n) instead of n separate O(log n) add() calls."""
        bit = cls(len(data))
        bit.tree[1:] = list(data)
        for i in range(1, bit.n + 1):
            parent = i + (i & -i)
            if parent <= bit.n:
                bit.tree[parent] += bit.tree[i]
        return bit


bit = FenwickTree.from_list([1, 3, 5, 7, 9, 11])
print(bit.prefix_sum(4))       # 16
print(bit.range_sum(2, 4))     # 15
bit.add(2, 10)                 # data[2] += 10
print(bit.range_sum(2, 4))     # 25

Fenwick versus segment tree. The Fenwick tree is strictly less general and, when it applies, strictly better:

The critical limitation is in bold: range_sum(l, r) = prefix_sum(r) − prefix_sum(l−1) requires an inverse. There is no inverse for min, so you cannot build a range-minimum Fenwick tree the same way. That, and nothing else, is what forces you to a segment tree.

Two extensions worth knowing:

• Range update, point query — keep a BIT of differences. add(l, r, delta) becomes bit.add(l, delta); bit.add(r + 1, -delta), and point_query(i) is bit.prefix_sum(i).
• Range update, range sum — two BITs, using the identity that a difference array’s prefix-of-prefix reconstructs the running total. Still O(log n) with half the memory of a lazy segment tree.
• Find the smallest i with prefix_sum(i) ≥ k — a binary lift over the BIT in a single O(log n) descent (not O(log² n)), which makes a Fenwick tree over value-frequencies an order-statistic structure.

Fenwick trees are also how you count inversions in O(n log n): sweep left to right, and for each element count how many larger values you have already inserted.

Suffix arrays and suffix trees

The last family answers substring queries on a text you will search repeatedly. Searching a text of length n for a pattern of length m once is best done with KMP or Boyer–Moore in O(n + m) — do not build a suffix structure for a single search. But if the text is fixed and the queries keep coming, preprocessing every suffix pays off immediately.

A suffix array is simply the sorted order of all n suffixes of the text, stored as their starting indices:

s = "banana"

suffix        index      sorted           suffix array
"banana"        0        "a"        (5)        sa = [5, 3, 1, 0, 4, 2]
"anana"         1        "ana"      (3)
"nana"          2        "anana"    (1)        lcp = [0, 1, 3, 0, 0, 2]
"ana"           3        "banana"   (0)              (LCP with the previous suffix)
"na"            4        "na"       (4)
"a"             5        "nana"     (2)

Because the suffixes are sorted, every occurrence of a pattern p appears as a contiguous block in the suffix array — all suffixes starting with p sort together. So substring search is two binary searches.

def build_suffix_array(s):
    """Suffix array of s by prefix doubling: O(n log^2 n).

    Invariant: after the iteration with step k, `rank` ranks every suffix by
    its first 2k characters. Doubling k until it exceeds n ranks them fully.
    """
    n = len(s)
    sa = list(range(n))
    rank = [ord(c) for c in s]          # rank by the first character
    k = 1
    while k < n:
        # sort by (rank of first k chars, rank of the next k chars)
        key = lambda i: (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)                # O(n log n) per round, log n rounds
        new_rank = [0] * n
        for i in range(1, n):
            new_rank[sa[i]] = new_rank[sa[i - 1]] + (key(sa[i]) > key(sa[i - 1]))
        rank = new_rank
        k *= 2
    return sa


def find_range(s, sa, pattern):
    """(lo, hi) half-open range of suffix-array slots whose suffix starts with
    pattern. O(|pattern| * log |s|): log n comparisons, each O(|pattern|)."""
    m = len(pattern)
    lo, hi = 0, len(sa)
    while lo < hi:                              # lower bound
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid] + m] < pattern:
            lo = mid + 1
        else:
            hi = mid
    start, hi = lo, len(sa)
    while lo < hi:                              # upper bound
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid] + m] <= pattern:
            lo = mid + 1
        else:
            hi = mid
    return start, lo


s = "banana"
sa = build_suffix_array(s)
print(sa)                                   # [5, 3, 1, 0, 4, 2]
lo, hi = find_range(s, sa, "ana")
print(hi - lo, sorted(sa[lo:hi]))           # 2 [1, 3]  — "ana" occurs at 1 and 3

The doubling construction above is O(n log² n) because it re-sorts each round; replacing the sort with a radix sort gives O(n log n), and the SA-IS algorithm builds it in O(n) and is what real libraries use. For a note like this, the doubling version is the one worth being able to write from memory.

A companion LCP array — lcp[i] = length of the longest common prefix of sa[i] and sa[i−1] — is built in O(n) by Kasai’s algorithm and unlocks most of the interesting queries:

• Longest repeated substring = the largest value in the LCP array.
• Number of distinct substrings = n(n+1)/2 − sum(lcp).
• Longest common substring of two strings = concatenate them with a separator that appears in neither, build the suffix array, and find the largest LCP between adjacent suffixes coming from different halves.

A suffix tree is the compressed trie of all suffixes of the text (with a terminator appended so no suffix is a prefix of another). It has exactly n leaves — one per suffix — and at most n−1 internal nodes, so O(n) nodes total despite representing O(n²) characters worth of suffixes, because edges store (start, end) index pairs into the original text rather than copies.

suffix tree for "banana$"        (edge labels are substrings of the text)

              (root)
       /        |        \      \
    "a"      "banana$"  "na"    "$"
    / \                 /  \
"na" \"$"          "na$"   "$"
  / \
"na$" "$"

Ukkonen’s algorithm builds a suffix tree in O(n), and it answers “does p occur?” in O(m) — optimal, and better than the suffix array’s O(m log n). In practice, suffix arrays still win almost every time:

The suffix array is the pragmatic choice: same power for nearly all queries, a fraction of the memory, dramatically simpler code, and better constants. Suffix arrays plus the Burrows–Wheeler transform are the basis of the FM-index, which is how genome aligners (Bowtie, BWA) search a 3-gigabase reference in compressed form.

Which range-query structure should I use?

This is the practical payoff of the whole note. Pick by two questions: does the data change? and is the operation invertible?

The most common mistake is skipping the first two rows. An enormous fraction of “I need a segment tree” problems are static, and a prefix-sum array solves them in three lines with O(1) queries.

Best Practices

• Do not build a trie for membership testing. A set of strings is smaller, faster, and one line. Build a trie when you need prefix semantics — autocomplete, longest-prefix-match routing, ordered iteration over a keyspace — because that is the only thing it does that nothing else does.
• Compress your trie if it goes to production. A plain trie over long keys is mostly single-child chains. A radix trie has O(n) nodes instead of O(N) characters and is what every real system (routing tables, etcd, Redis rax) actually ships.
• Choose the trie’s child representation deliberately. Array-of-Σ for a small dense alphabet, a hash map for sparse or Unicode keys, a bitmap for memory-critical code. This one decision dominates the trie’s memory footprint.
• Check for a static solution before building a segment tree. If the array never changes, a prefix-sum array gives O(1) queries, and a sparse table gives O(1) range min/max. Both are simpler and faster than anything logarithmic.
• Verify your operation is a monoid before using a segment tree. You need associativity and an identity. “Sum”, “min”, “gcd”, “max subarray sum” all work. “Median of the range” and “k-th largest” do not, because two children’s answers do not compose into the parent’s.
• Prefer a Fenwick tree whenever the operation is invertible. Quarter the memory, a third of the code, a much better constant factor. Move to a segment tree only when you hit min/max/non-invertible merges or need range updates with lazy propagation.
• Get the Fenwick indexing right once and never touch it again. It is 1-based. prefix_sum(0) must return 0. range_sum(l, r) = prefix_sum(r) − prefix_sum(l−1). Off-by-one errors here are the standard BIT bug.
• Build a Fenwick tree in O(n), not O(n log n). The in-place from_list construction above is three lines and strictly better than calling add n times.
• When writing lazy propagation, define composition explicitly. Write down how two pending updates combine, and whether order matters, before writing code. Mixing “range assign” with “range add” without a stated composition rule is the single most reliable way to produce a segment tree that is wrong only on large inputs.
• Use a suffix array, not a suffix tree, unless you specifically need O(m) search and have measured that O(m log n) is too slow. Same power for almost every query, an order of magnitude less memory, and code you can actually debug.
• Do not preprocess a text you will search once. Building a suffix array is O(n) at best with a large constant; KMP finds a single pattern in O(n + m) with no preprocessing of the text at all.
• Know what your language already gives you. Python has no built-in segment tree or trie, but bisect covers sorted-array searches, collections.Counter and dict cover most frequency work, and for large numeric range queries numpy.cumsum is a prefix-sum array with a C constant factor. Reach for the custom structure only when the built-ins genuinely cannot express the query.

References

• roadmap.sh — Data Structures & Algorithms
• Trie — Wikipedia
• Radix tree (PATRICIA trie) — Wikipedia
• cp-algorithms — Segment Tree
• Segment tree — Wikipedia
• cp-algorithms — Fenwick Tree
• Fenwick tree — Wikipedia
• cp-algorithms — Suffix Array
• Suffix array — Wikipedia
• Suffix tree — Wikipedia
• Burrows–Wheeler transform — Wikipedia
• CLRS — Introduction to Algorithms
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• VisuAlgo — Fenwick Tree
• Python Documentation — bisect