题目链接：https://www.nowcoder.com/acm/contest/148/A
题意：有函数f(x)它的值有一半概率是x - lowbit(x)，一半概率是x + lowbit(x)。现在给出数组A[]对其有两种操作：①.给[L,R]区间内Ai赋值为f(A[i])；②.查询区间[L,R]内Ai和的期望。
解析：由于每个被操作的元素减和加的概率相同，所以期望值不变。直接无视操作1，直接执行操作2，问题变为简单的区间求和。
线段树代码（117ms）：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxN=1e5+105;
const ll mod=998244353;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1ll tree[maxN<<2];
ll n,m,op,x,y;inline void pushup(ll rt)
{tree[rt]=(tree[rt<<1]+tree[rt<<1|1])%mod;
}
void build(ll l,ll r,ll rt)
{if(l==r){scanf("%lld",&tree[rt]);return;}ll m=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
ll sum(ll L,ll R,ll l,ll r,ll rt)
{if(L<=l&&r<=R){return tree[rt];}ll m=(l+r)>>1;ll ret=0;if(L<=m) ret=(ret+sum(L,R,lson))%mod;if(R>m) ret=(ret+sum(L,R,rson))%mod;pushup(rt);return ret;
}ll pow_mod(ll n,ll k,ll mod)//快速幂求n^k余m的结果
{ll res=1;n=n%mod;while(k>0){if(k&1)res=res*n%mod;n=n*n%mod;k>>=1;}return res;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%lld%lld",&n,&m);build(1,n,1);for(int i=1;i<=m;i++){scanf("%lld%lld%lld",&op,&x,&y);if(op==2){ll ans=sum(x,y,1,n,1)%mod;ans=ans*pow_mod(2ll,n*m,mod)%mod;printf("%lld\n",ans%mod);}}}return 0;
}树状数组代码（246ms）：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+105;
const ll mod=998244353;ll n,m,op,x,y,val,tree[MAXN];ll lowbit(ll i)
{return i&(-i);
}
void add(ll i,ll v)
{while(i<=n){tree[i]=(tree[i]+v)%mod;i+=lowbit(i);}
}
ll sum(ll i)
{ll res=0;while(i>0){res=(res+tree[i])%mod;i-=lowbit(i);}return res;
}
ll pow_mod(ll n,ll k,ll mod)//快速幂求n^k余m的结果
{ll res=1;n=n%mod;while(k>0){if(k&1)res=res*n%mod;n=n*n%mod;k>>=1;}return res;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%lld%lld",&n,&m);memset(tree,0,sizeof(tree));for(int i=1;i<=n;i++){scanf("%lld",&val);add(i,val);//add(i+1,-1ll*val);}for(int i=1;i<=m;i++){scanf("%lld%lld%lld",&op,&x,&y);if(op==2){ll ans=(sum(y)-sum(x-1)+mod)%mod;ans=ans*pow_mod(2ll,n*m,mod)%mod;printf("%lld\n",ans%mod);}}}return 0;
}