Ta sẽ xử lý các truy vấn theo chiều ~r~ tăng dần.

Với mỗi phần tử từ ~1~ tới ~i~, ta sẽ lưu vị trí xuất hiện cuối cùng của nó. Ví dụ: nếu ta xử lý đến ~[3, 2, 1, 1, 3]~, ta sẽ lưu lại thành ~[0, 2, 0, 1, 3]~.

Sau đó, để trả lời truy vấn ~(l, i)~, ta chỉ cần lấy phép ~\text{xor}~ các số trong đoạn ~[l..i]~. Cả hai thao tác cập nhật và trả lời truy vấn đều có thể xử lý bằng fenwick tree.

Độ phức tạp: ~O((n + q)\ \text{log}\ n)~.