## Editorial for UTS Open '18 P6 - Subset Sum

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: PlasmaVortex

The condition is equivalent to and , which can be checked on time (here, denotes the bitwise AND operation). For each type query, we can loop through all subsets and add its value to the total if it satisfies this condition.

Time Complexity: If we treat the identifiers as vertices of an -dimensional hypercube, we can create an -dimensional prefix sum array in by calculating a prefix sum in each dimension. More specifically, for each  , for all integers with bit , add arr to arr . Now arr will be the sum of the values of all such that .

Split the queries into blocks of size . At the start of each block, initialize the prefix sum array as above. Keep a list of the updates that have occurred, and when querying a set , return arr with adjustments for any set whose value was updated (there are at most of them if you reset the list of updates each block).

Time Complexity: Let denote the bit of . For each query , we need , otherwise the answer to the query would be . This means there are possibilities for : either , , or . Let and be the first and second halves of the binary representation of an integer . We can 'join' the and to get a ternary number , where the digit of is if , if , or if . Similarly, we can convert back, going from any -digit ternary integer to a corresponding pair of -bit integers and , with and .
Now, define the array arr as the sum of the values of all -bit integers , whose second half (in binary) is , and whose first half satisfies and , where and are the pair of integers such that and . When the value of changes by , we can update this array in by adding to arr , for all such that and (there are exactly such pairs ). To answer the query , we add up arr for all such that and , which is also . Note that we can precalculate in , and array arr can be efficiently initialized in (alternatively, you can initialize with all 's and update times).
Time Complexity: 