Shoeib's blog

XOR Basis with deletion
By Shoeib, history, 4 months ago, In English

Is it possible to implement XOR Basis with deletion whether online or offline?
If it's possible can someone share an implementation?

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
4 months ago, hide # |
← Rev. 2  
Vote: I like it -22 Vote: I do not like it

I think operations are idempotent. Because let's say you generate a basis. There are 2^basis size possible.

I guess you can do the same thing as you do on idempotent functions. Like what would you do calculate range and, or. You work on intervals. Same thing you can do here.

→ Reply
»
4 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

You can find it here

→ Reply
»
4 months ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Deletions of specific values can be done offline with divide & conquer over time. Track when each value is “alive” as an interval $$$[l,r]$$$, add it to every segtree node whose segment lies fully inside $$$[l,r]$$$, then DFS the segtree with a rollback xor-basis. The basis at time $$$i$$$ is exactly what you have at the $$$i$$$-th leaf.

If online queries are forced, you can use this method. It runs in around $$$O(B^2)$$$ per op, so its slower than the d&c for sure.

Side Note: Another trick I find useful is “recency bias” over vectors. When inserting, also store a time/position. If a vector with the same leading bit already exists, compare times: if the incoming one is more recent, swap them so the basis keeps the newer vector, and keep inserting the older one; otherwise xor and continue. Definitely useful for span queries over contiguous ranges when you process queries offline.

Some problems to look at:

2116F - Gellyfish and Forget-Me-Not

1100F - Ivan and Burgers

1902F - Trees and XOR Queries Again

→ Reply