tl;dr: NFA transition functions form a monoid under composition. By using balanced ropes as a monoid-cached tree, we can get incremental regular expression matching in O(lg n) time for a string of length n undergoing a one-character change (for a given automaton), and O(n) for a string undergoing an n-character change.
And if that didn't make perfect sense, read the article. It's one of the best things to appear on Hacker News in quite a while.