分析
首先，数组大小为 \(2^n\)，所以可以确保2和3操作都能覆盖到整个数组，而且我们可以将整个数组分为 \(n+1\) 层。
在分层之后，我们该怎么处理2操作和3操作呢？首先理解3操作，将题面简化就是将每个大小为 \(2^{k+1}\) 里面的左右两块整体交换，在此基础上，我们就可以进一步理解2操作，相当于 $i 从 \(k\) 一直到1，将大小为 \(2^i\) 内的左右两部分整体交换，可以自己画个草图理解一下。
对于大小为 \(2^i\) 的左右调换如何简化呢，上面已经说了，2和3操作能覆盖整个数组，因此对于这样的一个调换，我们可以对第 \(i\) 层打上标记，那我们在修改和查值时，如果询问到这一层，对于线段树就可以理解为它的左儿子和右儿子进行了调换，如果有标记就去本不会去的那一个儿子就可以了。
具体操作可以看代码，目前最优解。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls (rt<<1)
#define rs ((rt<<1)^1)
int n,q,rot[20],a[600000],p;
inline void read(int &res){
res=0;
char c=getchar();
while(c<‘0‘||c>‘9‘)c=getchar();
while(c>=‘0‘&&c<=‘9‘)res=(res<<1)+(res<<3)+c-48,c=getchar();
}
void build(int l,int r,int rt){//左端点，右端点，编号
if(l==r){
read(a[rt]);//此处读入易证其正确性，就不证明了
return;
}
int mid=(l+r)>>1;
build(l,mid,ls),build(mid+1,r,rs);
a[rt]=a[ls]+a[rs];//取和
}
inline void modify(int mb,int L,int R,int rt,int fz,int ccs){//目标位置，左端点，右端点，区间编号，欲修改值，层数
if(L==R){//找到目标位置，进行修改
a[rt]=fz;
return;
}
int mid=(L+R)>>1;
if(mid>=mb)modify(mb,L,mid,ls^rot[ccs],fz,ccs-1);//异或即可改变是否去另一个子区间
if(mid<mb)modify(mb,mid+1,R,rs^rot[ccs],fz,ccs-1);
a[rt]=a[ls]+a[rs];
}
int query(int l,int r,int L,int R,int rt,int ccs){//目标左端点，目标右端点，左端点，右端点，区间编号，层数
if(L>=l&&r>=R)return a[rt];
int mid=(L+R)>>1,ll=0,rr=0;
if(mid>=l)ll=query(l,r,L,mid,ls^rot[ccs],ccs-1);
if(mid<r)rr=query(l,r,mid+1,R,rs^rot[ccs],ccs-1);
return ll+rr;
}
signed main()
{
read(n);read(p);
int xx=1<<n;
build(1,xx,1);
int op,ll,rr;
for(register int i=1;i<=p;i++){
read(op);
if(op==1){
read(ll);read(rr);
modify(ll,1,xx,1,rr,n);
}
if(op==2){
read(ll);
for(int i=0;i<=ll;i++)rot[i]^=1;
}
if(op==3){
read(ll);rot[ll+1]^=1;
}//2、3操作的含义于题目中已解释过了
if(op==4){
read(ll);read(rr);
printf("%lld\n",query(ll,rr,1,xx,1,n));
}
}
return 0;
}