PROBLEM LINK:Author: Kamil Debowski DIFFICULTY:medium PREREQUISITES:segment tree, understanding of bit wise xor operations PROBLEM:Given an array $a$ containing $n$ positive integers between 0 and 50, find the xor of sums of all nonempty segments of the array. In other words, for each of $\binom{n}{2} + n$ nonempty subarrays (consecutive subsequences) find its sum of elements, and print the xor of those sums. Let's start with the bruteforce solution that won't pass.Let $a[i, j]$ denote the subarray $a_i, a_{i+1}, \dots, a_j$. We iterate over all subarrays $a[i, j]$ and find their sum in constant time by precomputing prefix sums, and thus compute the xor of these sums. This approach has a time complexity of $\mathcal{O}(n^2)$ which has no chance of passing as $n$ can be as large as $3 \cdot 10^5$. An important observationClaim: For a number $x$, its $b$th bit (zero based indexing from least significant digit to highest significant digit) will be set if and only if $x \text{ mod } {2^{b+1}} \geq 2^b$. Think in terms of finding the bits of the answerWhen dealing with bitwise operations, it is generally a good idea to finding the bits of the answer. We want to check whether a particular $b$th bit of the answer is set (1) or not. If the number of subarrays with $b$th bit set in their sum is odd, then $i$th bit in the answer will be 1, 0 otherwise. This is due to properties of xor function. Xor of same bits is zero. If there are even number of 1's, then the xor will be zero, 1 otherwise. So, it means that if we can efficiently find the number of subarrays with $b$th bit set in their sum, then we can find the answer. Solving the reduced version of the problemLet $s$ be the prefix sum array for array $a$, modulo $2^{b+1}$. Assume $a$ has 1based indexing and $s$ 0based. We define $s_0 = 0$ and $s_i = (a_1 + a_2 + \dots + a_i) \text{ mod } 2^{b + 1}$. You can see that sum of subarray $a[j, i]$ modulo $2^{b+1}$ will be $(s_i  s_{j1}) \pmod {2^{b+1}}$. Finding total number of subarrays with $b$th bit set in their sum will be equivalent to finding number of pairs $(j, i)$ where $1 \leq j \leq i \leq n$, such that $(s_i  s_{j1}) \pmod{2^{b+1}} \geq 2^b$. We need to take care of following two cases.
Notice that the range $[0, s_i  2^b]$ and $[s_i + 1, s_i + 2^b]$ are mutually disjoint. This means that if we are able to find number of $s_{j1}$'s that belong to these ranges, we will be able to find the number of valid $j$'s for the index $i$. Segment tree to help answering the range queries fastYou can see that for finding number of valid $j$'s for a given $i$, we will need to answer queries in which we have to tell the number of elements of the array $s$ (only consider the numbers from the index $0$ to $i1$) that lie in a particular range. We can answer such queries using segment tree. The elements of $s$ lie between $0$ to $max_{s_i}$, where $max_{s_i}$ can be at max $a_1 + a_1 + \dots + a_n$. Let us denote $a_1 + a_1 + \dots + a_n$ by $S$. Assume we have an array $cnt$ of size $S+1$, where $cnt_x$ denote the number of times number $x$ has appeared in the array $s[0, i1]$. Answering the query of count of numbers in the subarray $s[0, i1]$ that have their values in the range $[L, R]$, will be same as finding the sum $cnt_L + cnt_{L+1} + \dots + cnt_R$. When you go from $i$ to $i+1$, you will to increment $cnt_{s_{i}}$ by 1. Effectively, you need to maintain these two operations over an array of size $S$+1.
Both of these operations can be perfomed in $\mathcal{O}(\log{S})$ time using segment tree, where a node of the segment tree will store the sum of elements for the range it is responsible. Finally the solution with its time complexitySo, we can now count the number of valid $j$'s for all the $i$'s in $\mathcal{O}(n \cdot \log{S})$, i.e. we can find the number of the subarrays $a[j, i]$ with $b$th bit set. We will do this for each bit in the answer ($\log{S}$ bits). Hence, time complexity of this approach comes out to be $\mathcal{O}(n \cdot {\log{S}}^2)$ time. Memory complexity of the solution will be $\mathcal{O}(S)$ required for the segment tree to operate over $S$ elements. Pseudo Code
AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 22 Apr '17, 19:04

Hi everyone! Feel free to post any suggestions or doubts you might have in the comments. I will be making the second part of this soon. Cheers! answered 27 Apr '17, 13:37

Answer is hidden as author is suspended. Click here to view.
answered 30 Apr '17, 18:13
1
Thats getting the sum of numbers from 0 to index i, with the sum modulo 2^b. This allows us to ignore bits from MSB to b+1.
(02 May '17, 03:09)

@dpraveen
In "Solving the reduced version of the problem" section can you please explain the cases in more detail. I didn't understand the equality in both cases.
(s_{i}−s_{j−1})mod(2^{b+1})=s_{i}−s_{j1}
can you please explain the reason for this equality.
@arpit728: s_i >= s_{j1}, and s_i and s_j are both less than 2^{b+1}. So, this will be true.
@dpraveen
and what about the second condition. (s_{i}−s_{j−1})mod(2^{b+1})=s_{i}−s_{j−1}+2^{b+1}
The overall idea is as follows. Suppose there are two numbers a, b and mod such that $0 \leq a, b < mod$. We want to find value of $(a  b) \mod {mod}$.
There can be two cases.