Đây là bài toán về cấu trúc dữ liệu.

Đầu tiên, ta chia tập hợp thành các tập nặng và nhẹ. Tập nhẹ là các tập chứa ít hơn ~\sqrt{n}~ phần tử, các tập còn lại sẽ là tập nặng.

Nhận xét rằng mỗi tập nhẹ sẽ chứa ít hơn ~\sqrt{n}~ phần tử và số lượng tập nặng không vượt quá ~\sqrt{n}~ bởi vì ta có cận trên cho tổng kích thước của các tập. Để trả lời các truy vấn một cách hiệu quả, với mỗi tập (cả nặng và nhẹ) ta cần tính toán kích thước phần giao của tập này với từng tập nặng.

Ta có thể thực hiện thao tác với độ phức tạp thời gian và bộ nhớ ~O(n\sqrt{n})~. Đối với mỗi tập nặng chúng ta tạo mảng boolean gồm ~n~ phần tử. Ở vị trí ~i~ của mảng này, ta lưu liệu phần tử ~i~ hiện đang trong tập đã có hay chưa. Khi này đối với mỗi phần tử và mỗi tập nặng, ta có thể kiểm tra trong thời gian ~O(1)~ rằng phần tử đó có nằm trong tập đang xét hay không.

Ta xét 4 trường hợp có thể xảy ra:

• Thêm vào tập nhẹ: Duyệt qua mọi phần tử trong tập và thêm giá trị từ truy vấn vào từng phần tử đó. Sau đó duyệt qua tất cả tập nặng và thêm vào tổng một lượng bằng với kích thước của phần giao nhân với giá trị từ truy vấn. Độ phức tạp thời gian là ~2\sqrt{n} = O(\sqrt{n})~.

• Thêm vào tập nặng: chỉ cần cập nhật tổng cho tập nặng. Độ phức tạp thời gian là ~O(1)~.

• Trả lời truy vấn cho tập nhẹ: Duyệt qua hết số trong tập hợp và thêm giá trị vào câu trả lời. Sau đó duyệt qua tất cả các tập nặng và thêm vào câu trả lời một lượng bằng câu trả lời cho tập nặng này nhân với kích thước phần giao với set trong truy vấn. Độ phức tạp thời gian là ~2\sqrt{n} = O(\sqrt{n})~.

• Trả lời truy vấn cho tập nặng: Lấy tổng đã tính, sau đó duyệt qua tất cả tập nặng và thêm vào câu trả lời một lượng bằng tổng của tập nặng này nhân cho kích thước phần giao với tập trong truy vấn. Độ phức tạp thời gian là ~2\sqrt{n} = O(\sqrt{n})~.

Ta có ~q~ truy vấn nên tổng độ phức tạp là ~O(q\sqrt{n})~.