Algorithm for doing many substring reversals?

Question

Suppose I have a string S of length N, and I want to perform M of the following operations:

• choose 1 <= L,R <= N and reverse the substring S[L..R]

I am interested in what the final string looks like after all M operations. The obvious approach is to do the actual swapping, which leads to O(MN) worst-case behavior. Is there a faster way? I'm trying to just keep track of where an index ends up, but I cannot find a way to reduce the running time (though I have a gut feeling O(M lg N + N) -- for the operations and the final reading -- is possible).

Answer 1

Yeah, it's possible. Make a binary tree structure like

struct node {
    struct node *child[2];
    struct node *parent;
    char label;
    bool subtree_flipped;
};

Then you can have a logical getter/setter for left/right child:

struct node *get_child(struct node *u, bool right) {
    return u->child[u->subtree_flipped ^ right];
}

void set_child(struct node *u, bool right, struct node *c) {
    u->child[u->subtree_flipped ^ right] = c;
    if (c != NULL) { c->parent = u; }
}

Rotations have to preserve flipped bits:

struct node *detach(struct node *u, bool right) {
    struct node *c = get_child(u, right);
    if (c != NULL) { c->subtree_flipped ^= u->subtree_flipped; }
    return c;
}

void attach(struct node *u, bool right, struct node *c) {
    set_child(u, right, c);
    if (c != NULL) { c->subtree_flipped ^= u->subtree_flipped; }
}

// rotates one of |p|'s child up.
// does not fix up the pointer to |p|.
void rotate(struct node *p, bool right) {
    struct node *u = detach(p, right);
    struct node *c = detach(u, !right);
    attach(p, right, c);
    attach(u, !right, p);
}

Implement splay with rotations. It should take a "guard" pointer that is treated as a NULL parent for the purpose of splaying, so that you can splay one node to the root and another to its right child. Do this and then you can splay both endpoints of the flipped region and then toggle the flip bits for the root and the two subtrees corresponding to segments left unaffected.

Traversal looks like this.

void traverse(struct node *u, bool flipped) {
    if (u == NULL) { return; }
    flipped ^= u->subtree_flipped;
    traverse(u->child[flipped], flipped);
    visit(u);
    traverse(u->child[!flipped], flipped);
}