数据结构Spaly_Tree(二)
护X结点
if(f==0)//更新根结点
{
root=x;
}
}
void Rotate_Under(int k,int f)//把第k位的数伸展到f下方
{
//找到处在中序遍历第k个结点，并将其旋转到结点f 的下面
int p=root;//从根结点开始
Push_Down(p);// 由于要访问p的子结点，将标记下传
while(size[ch[p][0]]!=k)//p的左子树的大小
{
if(k
{
p=ch[p][0];
}
else//否则在右边,而且在右子树中，这个结点不再是第k个
{
k-=(size[ch[p][0]]+1);
p=ch[p][1];
}
Push_Down(p);
}
Splay(p,f);//执行旋转
}
int Insert(int k)//插入结点
{
int r=root;
while(ch[r][key[r]
r=ch[r][key[r]
New_Node(ch[r][k>key[r]],r,k);
//将新插入的结点更新至根结点
//Push_Up(r);
Splay(ch[r][k>key[r]],0);
return 1;
}
int Get_Pre(int x)//找前驱，即左子树的最右结点
{
int tmp=ch[x][0];
if(tmp==0)
return INF;
while(ch[tmp][1])
{
tmp=ch[tmp][1];
}
return key[x]-key[tmp];
}
int Get_Next(int x)//找后继，即右子树的最左结点
{
int tmp=ch[x][1];
if(tmp==0)
return INF;
while(ch[tmp][0])
{
tmp=ch[tmp][0];
}
return key[tmp]-key[x];
}
LL Query(int l,int r)//查询[l,r]之间的和
{
Rotate_Under(l-1,0);
Rotate_Under(r+1,root);
return sum[Key_value];
}
void Update(int l,int r)//更新
{
int k;
scanf("%d",&k);
Rotate_Under(l-1,0);
Rotate_Under(r+1,root);
add[Key_value]+=k;
sum[Key_value]+=size[Key_value]*k;
}
void Init()//初始化
{
for(int i=0; i
scanf("%d",&a[i]);
ch[0][0]=ch[0][1]=pre[0]=size[0]=0;
add[0]=sum[0]=0;
root=tot=0;
New_Node(root,0,-1);
New_Node(ch[root][1],root,-1); //头尾各加入一个空位
size[root]=2;
Build_Tree(Key_value,0,n-1,ch[root][1]); //让所有数据夹在两个-1之间
Push_Up(ch[root][1]);
Push_Up(root);
}
int main()
{
//freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
while(~scanf("%d%d",&n,&q))
{
Init();
while(q--)
{
char op;
scanf(" %c",&op);
int x,y;
scanf("%d%d",&x,&y);
if(op=='Q')
printf("%lld\n",Query(x,y));
else
Update(x,y);
}
}
return 0;
}