Chúng ta có thể sử dụng ~Trie~ để giải quyết bài toán này.

Mỗi ~node~ của ~Trie~ ta sẽ lưu các thông tin sau:

- Vị trí của các ~node~ con.

- Biến ~cnt~ lưu số giá trị trong tập ~S~ đi qua ~node~ này.

- Biến ~sum~ lưu tổng các giá trị trong tập ~S~ đi qua ~node~ này.

Sau đó, với mỗi truy vấn, ta giải như sau:

- Đối với truy vấn ~1~, ta sẽ phân tích số ~x~ về hệ cơ số ~2~, rồi thêm vào ~Trie~ theo thứ tự ~bit~ từ lớn đến bé. Mỗi lần đi qua một ~node~, ta cộng giá trị ~cnt~ của ~node~ đó lên ~1~ và giá trị ~sum~ lên ~x~.

- Đối với truy vấn ~2~, ta sẽ thực hiện xóa như bình thường, mỗi lần đi qua một ~node~ ta giảm giá trị ~cnt~ của ~node~ đó đi ~1~ và giá trị ~sum~ đi ~x~.

- Đối với truy vấn ~3~, ta gọi hàm ~sum(n)~ là tổng các ~S_i \le n~. Như vậy kết quả của truy vấn sẽ là ~sum(R) - sum(L-1)~. Để tính hàm ~sum(n)~, ta sẽ đi theo từng ~bit~ của ~n~, giả sử ~bit_i~ của ~n~ bằng ~1~, ta sẽ cộng giá trị ~sum~ của ~node~ chứa ~bit_i = 0~ và sau đó đi vào ~node~ chứa ~bit_i = 1~.

- Đối với truy vấn ~4~, dựa vào giá trị ~cnt~ của mỗi ~node~, ta có thể ~walk~ trên ~Trie~ như trên ~Segment~ ~Tree~.

- Đối với truy vấn ~5~, dựa vào tính chất của phép ~xor~, ta sẽ ưu tiên đi vào những ~node~ chứa ~bit~ nghịch của ~a~ nếu có thể. Ví dụ ~bit_i = 0~, ta sẽ ưu tiên đi vào ~node~ chứa ~bit_i = 1~, nếu được thì cộng vào đáp án ~2^i~, tương tự với trường hợp ~bit_i = 1~. Nếu không thể đi vào ~bit~ nghịch, ta tiếp tục đi vào ~bit~ đó nhưng không cộng thêm vào đáp án.