Xor Rectangle

You have an array of N integers 

$S_1,S_2,...S_N$. Consider a N x N matrix such that $A_{i,j}=S_i\oplus S_j$. Here $\oplus$ indicates bitwise xor operator.
You have been given Q queries. Each query consists of four integers $x_1,y_1,x_2,y_2$ which denotes a submatrix with ($x_1,y_1$) as their top-left corner and ($x_2,y_2$) as their bottom-right corner such that $x_1\le x_2$ and $y_1\le y_2$. For each of the query, you have to print summation of all integers lying in queried submatrix.

Example:

Input:  n = 4, a = {1, 2, 3, 4},q = 2, queries = {{1, 2, 3, 4}, {1, 1, 1, 1}}

Output:

25
0

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

int arr[1000005];
int tree[1000005][20];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n = 4;
    vector<int> a = {1, 2, 3, 4};
    int q = 2;
    vector<vector<int>> queries = {{1, 2, 3, 4},
                                   {1, 1, 1, 1}};

    for (int i = 1; i <= n; i++)
    {
        arr[i] = a[i - 1];
    }

    int x1, x2, y1, y2;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 20; j++)
        {
            tree[i][j] = tree[i - 1][j] + (1 & (arr[i] >> j));
        }
    }

    for (int i = 0; i < q; i++)
    {
        x1 = queries[i][0];
        y1 = queries[i][1];
        x2 = queries[i][2];
        y2 = queries[i][3];

        long long ans = 0;
        int w = x2 - x1 + 1, h = y2 - y1 + 1, a, b;

        for (int i = 0; i < 20; i++)
        {
            a = (tree[x2][i] - tree[x1 - 1][i]);
            b = (tree[y2][i] - tree[y1 - 1][i]);

            ans += (1LL << i) * (a * (h - b) + b * (w - a));
        }

        cout << ans << "\n";
    }

    return 0;
}