Effective rope re-mixing

Question

Given rope , let's say we need to know its hash (passing the concatenation of all leaves through some hash function).

Now that one leaf of the rope is changing, what is the effective way to recalculate the hash of the whole rope again? That is, something like O (log n) instead of O (n).

One way would be to use a Merkle tree . However, this leads to problems such as ...

• Empty non-leaf nodes or leaf nodes with substrings of zero length affect the hash, even if they do not affect the content of the effective cable;
• Moving nodes to the right of the subtree to the left of this subtree to the right on the sibling side affects the final hash, but not the effective contents of the cable.

Is there a better algorithm for this? The hash function should not be cryptographically secure, good enough to avoid potential collisions.

Answer 1

Just as any node of the cable stores the size of the left subtree (or itself if it is a leaf), any node can additionally store a polynomial hash of the string corresponding to the left subtree (or itself if it is a leaf).

When the weight is recalculated for a node, the hash is also recalculated for that node with the same asymptotic complexity.

For example, let the nodes and values ​​in them:

    left     right    string     weight
1:                     abcd         4
2:    1        4                    4
3:                     ef           2
4:    3        5                    2
5:                     ghi          3

A polynomial hash with some fixed constants p and q:

h (s [0] s [1]... s [n-1]) = (s [0] * p ^ (n-1) + s [1] * p ^ (n-2) +... + s [n-1] * p ^ 0) mod q.

, , q:

         hash
1:  a*p^3 + b*p^2 + c*p^1 + d*p^0
2:  a*p^3 + b*p^2 + c*p^1 + d*p^0
3:  e*p^1 + f*p^0
4:  e*p^1 + f*p^0
5:  g*p^2 + h*p^1 + i*p^0

---

q. q. , q. ,

(a? b) mod q = ((mod q)? (b mod q)) mod q

? , . , , , mod q, . , p q 2 ³⁰= 1 073 741 824, 32- , 64- . q, 32- .

---

, - , - node ?

, . , (, q):

({a * p ^ 3 + b * p ^ 2 + c * p ^ 1 + d * p ^ 0} * p ^ 2 + {e * p ^ 1 + f * p ^ 0}) * p ^ 3 + {g * p ^ 2 + h * p ^ 1 + i * p ^ 0}

- , . . , , , p ( p ^ 3 p ^ (3 + 2 = 5)) .

:

a * p ^ 8 + b * p ^ 7 + c * p ^ 6 + d * p ^ 5 + e * p ^ 4 + f * p ^ 3 + g * p ^ 2 + h * p ^ 1 + i * p ^ 0

---

.

• , , , p q, .

• , , , node. , , , , O (1), , O (log n), treap . , - node, , .

• ,
  h (s [0] s [1]... s [n-1]) = (s [0] * p ^ 0 + s [1] * p ^ 1 +... + s [n-1] * p ^ (n-1)) mod q,
  , node , .