支持范围求和和连续元素交换操作的最佳数据结构？

Question

我们有一组 n 个正整数和 m 个查询。每个查询可以是以下两种类型之一。

求出某个范围内所有元素的总和[i, j]
重新排序范围 [i, j] 中给定的元素，这样数组元素就会像这样

(a[i+1],a[i],a[i+3],a[i+2],..............,a[j],a[j-1]) 假定此范围长度为偶数。其中 a[i] 是 i 索引处的数组元素。

限制如下

2 ≤ n,m ≤ 2×10^5 

1 ≤ a[i] ≤ 10^6 

1≤ i ≤ j ≤n

我尝试使用线段树，但这些需要超过 2 秒。谁能建议最好的数据结构或任何最佳方法？

这是我的代码

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int sgtree[524288];
int data[200005];
int treeind[200005];
int constructSgTree(int start,int end,int index){
    if(start==end){
        sgtree[index]=data[start];
        treeind[start]=index;
        return data[start];
    }
    else{
        int mid=start+(end-start)/2;
        sgtree[index]=constructSgTree(start,mid,index*2+1)+constructSgTree(mid+1,end,index*2+2);
        return sgtree[index];
    }
}
int sumSgTree(int start,int end,int i,int j,int index){
    if(i<=start&&j>=end){
        return sgtree[index];
    }
    else if(i>end||j<start){
        return 0;
    }
    else{
            int mid=start+(end-start)/2;
            return sumSgTree(start,mid,i,j,2*index+1)+sumSgTree(mid+1,end,i,j,2*index+2);
    }
}
void updateSgTree(int start,int end,int i,int val,int index){

    if(i<start||i>end){
        return ;
    }
    else{
        sgtree[index]+=val;
        if(start!=end)
        {
        int mid=start+(end-start)/2;

        updateSgTree(start,mid,i,val,2*index+1);

        updateSgTree(mid+1,end,i,val,2*index+2);
            }

    }




}

int main() {
    int n,i,q,op,l,r,temp,j,temp1,temp2,temp3;
    cin>>n>>q;
    float sum=0;
    for(i=0;i<n;i++){
        cin>>data[i];
        //dataind[i]=i;
    }
    constructSgTree(0,n-1,0);
    /*
    for(i=0;i<n;i++){
        cout<<sgtree[treeind[i]]<<" ";
    }
    */
    //cout<<endl;
    for(i=0;i<q;i++){
        cin>>op>>l>>r;
        l--;
        r--;
        if(op==2){
            j=l;
            /*
            sum=0.0;
            while(j<=r){
                /*
                temp=data[j]-sgtree[treeind[j]];
                if(temp!=0){
                    updateSgTree(0,n-1,j,temp,0);
                }

                sum+=data[j];
                j++;

            }
            cout<<sum<<endl;
         */
            cout<<sumSgTree(0,n-1,l,r,0)<<endl;
        }
        else{
            while(l<=r){

                //temp=data[l+1]-data[l];
                if(l!=r){
                    temp=sgtree[treeind[l]];
                sgtree[treeind[l]]=sgtree[treeind[l+1]];
                sgtree[treeind[l+1]]=temp;
                temp1=(treeind[l]-1)/2;
                temp2=(treeind[l+1]-1)/2;



                    while(temp1!=temp2){
                        if(temp1<temp2){
                            sgtree[temp2]=sgtree[temp2]+data[l]-data[l+1];
                            temp2=(temp2-1)/2;
                        }
                        else{
                            sgtree[temp1]=sgtree[temp1]-data[l]+data[l+1];
                            temp1=(temp1-1)/2;
                        }
                    }
                    //updateSgTree(0,n-1,l,temp,0);
                    //updateSgTree(0,n-1,l+1,-temp,0);

                /*
                temp=data[l];
                data[l]=data[l+1];
                data[l+1]=temp;
                */
                temp=data[l];
                data[l]=data[l+1];
                data[l+1]=temp; 
                }

                l+=2;   
            }
        }
    }
    return 0;
}

Answer 1

你的解决方案的时间复杂度至少是每个查询O(n)（也许是O(n log n)），所以它显然太慢了。

这是一个每个查询需要 O(log n) 时间的解决方案：

让我们构建带有隐式键的 treaps：第一个将包含具有偶数索引的所有元素，第二个将包含具有奇数索引的所有元素。两棵树都应根据给定数组中的索引对元素进行排序。
总和查询非常简单：我们知道范围内最小和最大的奇数和偶数索引，因此我们可以运行在第一棵和第二棵树上进行此查询，然后return总和。
可以按以下方式处理交换查询：让我们将第一棵树分成 L1, M1, R1 部分，将第二棵树分成 L2, M2, R2（其中 M1 M2 是位于查询范围内的部分）。然后我们应该交换M1和M2并合并回来，即第一棵树是合并L1, M2, R1的结果，第二棵是L2, M1, R2。

每个查询都需要固定数量的合并和拆分操作，所以总时间复杂度是O((n + m) * log n)或O(n + m * log n)（这取决于我们在回答查询之前构建这些树的方式）。

支持范围求和和连续元素交换操作的最佳数据结构？

Best Data structure to support range Sum and consecutive elements swap operation?

algorithm

data-structures