C++程序使用按位或，在将给定数组拆分成两半并进行K次循环移位后找到数组和

给定长度为 N （其中 N 为偶数）的数组 A[] ，任务是回答 Q 个独立的查询，每个查询包含一个正整数 K ，表示在数组上执行的循环移位的次数，并通过在划分的数组上执行按位或操作找到元素的和。

注意： 每个查询都从原始数组开始。

例子：

输入： A[] = {12, 23, 4, 21, 22, 76}, Q = 1, K = 2

输出： 117

解释：

由于K是2，修改后的数组A[] = {22, 76, 12, 23, 4, 21}。

字节数组的前一半的按位或 = (22 | 76 | 12) = 94

字节数组的后一半的按位或 = (21 | 23 | 4) = 23

OR值的总和是94 + 23 = 117

输入： A[] = {7, 44, 19, 86, 65, 39, 75, 101}, Q = 1, K = 4

输出： 238

由于K是4，修改后的数组A[] = {65, 39, 75, 101, 7, 44, 19, 86}。

字节数组的前一半的按位或 = 111

字节数组的后一半的按位或 = 127

OR值的总和是111 + 127 = 238

Naive Approach:

要解决上述问题，最简单的方法是将数组的每个元素移动 K % (N / 2) 并遍历数组以为每个查询计算两个部分的OR。但是，该方法不是有效的，因此可以进一步优化。

Efficient Approach:

要优化上述方法，我们可以借助于段树数据结构。

Observation:

我们可以观察到，在恰好 N / 2 次右旋之后，数组的两半与原始数组相同。这将有效地将旋转次数减少为 K % (N / 2) 。
执行向右循环移位基本上是将数组的最后一个元素移动到前面。因此，对于任何正整数 X 执行 X 次右旋等于将数组的最后X个元素移动到前面。

以下是解决该问题的步骤：

为原始数组 A[] 构造一个段树，并分配一个变量，假设为 i = K % (N / 2) 。
对于每个查询，我们使用segment tree查询位OR；即从末尾开始的i个元素的按位OR结果 OR 前半部分 (N / 2) – i – 1 个元素的按位OR。
然后计算范围内元素的按位OR [(N / 2) – i, N – i – 1] 。
将两个结果相加以获取第i个查询的答案。

下面是上述方法的实现：

// C++程序，找到数组的两个相等的一半在执行K个右循环移位之后的位或
#include <bits/stdc++.h>
const int MAX = 100005;
using namespace std;
 
//用于存储线段树的数组
int seg[4 * MAX];
 
//建立线段树的函数
void build(int node, int l, int r, int a[])
{
    if (l == r)
        seg[node] = a[l];
 
    else {
        int mid = (l + r) / 2;
 
        build(2 * node, l, mid, a);
        build(2 * node + 1, mid + 1, r, a);
 
        seg[node] = (seg[2 * node]
                     | seg[2 * node + 1]);
    }
}
 
//返回一定范围内元素的OR的函数
int query(int node, int l, int r,
          int start, int end, int a[])
{
    //检查越界条件
    if (l > end or r < start)
        return 0;
 
    if (start <= l and r <= end)
        return seg[node];
 
    //找到范围的中间部分
    int mid = (l + r) / 2;
 
    //递归处理数组中的所有元素
    return ((query(2 * node, l, mid,
                   start, end, a))
            | (query(2 * node + 1, mid + 1,
                     r, start, end, a)));
}
 
//找到OR和的函数
void orsum(int a[], int n, int q, int k[])
{
    //建立线段树的函数
    build(1, 0, n - 1, a);
 
    //处理q个查询的循环
    for (int j = 0; j < q; j++) {
        //有效的循环右移数
        int i = k[j] % (n / 2);
 
        //计算来自分段树的两个数组半部分的OR
 
        // 数组的第二个半部分[n/2-i，n-1-i]的OR
        int sec = query(1, 0, n - 1,
                        n / 2 - i, n - i - 1, a);
 
        // 数组的第一个半部分[n-i，n-1] OR [0，n/2-1-i]
        int first = (query(1, 0, n - 1, 0,
                           n / 2 - 1 - i, a)
                     | query(1, 0, n - 1,
                             n - i, n - 1, a));
 
        int temp = sec + first;
 
        //打印查询的最终答案
        cout << temp << endl;
    }
}
 
//主函数
int main()
{
 
    int a[] = { 7, 44, 19, 86, 65, 39, 75, 101 };
    int n = sizeof(a) / sizeof(a[0]);
 
    int q = 2;
 
    int k[q] = { 4, 2 };
 
    orsum(a, n, q, k);
 
    return 0;
}

输出: