A - 单点修改区间查询 C++

本文主要是介绍A - 单点修改区间查询 C++，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End 

Case 1:
6
33
59

我们学长真的牛皮，他的那个update靓颖到我了，绝。

题目大意就是第一行输入一个t，然后代表t个测试案例，第二行输入n，然后在输入啊a1,a2,a3...an这样一个数组但是很重要的是，n小于5e4，要是暴力还有前缀和肯定会超时。。这时候线段树就出现了，然后输入完毕后，有三种指令，只要不是End就不会停止，输入Query后输入x和y值，意味下标为x-1到y-1的数之和，第二种指令Add后输入x和y值，意味着在下标为x-1的位置那个对应元素加上y，第三种指令Sub后输入x和y，意味着在下标 为x-1的位置对应元素减去y。以上就是题目大意。

AC代码：

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N=5e4+10;
int aa[N],record[N];

struct node{//每一个节点位置的状态，我们需要保存这个节点处的left到right的和sum，以及left和right
    int left,right,sum;
};

struct segment_tree{
    node s1[N<<2];//N*4

    void build_tree(int root,int left,int right){//重构树
        s1[root].left=left;//更新每一个节点的范围
        s1[root].right=right;
        if(left==right){//节点数到了最后left==right的时候就是找到了最根部
            s1[root].sum=aa[left];//找到之后，我们将对应【left，left】也就是aa[left]填入对应节点中
            record[left]=root;//保存我们将aa[left]填入的root位置
        }else{
            int temp=root<<1,mid=(right+left)>>1;//这个mid可以随便设置吧，只要mid在变化也可以，我学长这里用的是mid=left+right>>1;能够将一段分为两段同时到根部就可以；
            build_tree(temp,left,mid);//建立左树，每一个节点为什么变为root*2的形式是由于每个节点将分为两部分时，root会链接着root*2和root*2+1；画个图试试
            build_tree(temp+1,mid+1,right);//建立右树
            s1[root].sum=s1[temp].sum+s1[temp+1].sum;然后最后回溯所有的线段的长度
        }
    }

    int query(int root,int left,int right){//查询长度需要下标x和y，代表我们需要找到一个root的时候，他的范围是输入left到right的数据
        if(s1[root].left==left&&s1[root].right==right) return s1[root].sum;//我们需要一个来结束循环就是我们找到了结果
        int temp=root<<1,mid=(s1[root].left+s1[root].right)>>1;
        if(right<=mid)return query(temp,left,right);//当我们需要找的右端都比这个root范围的中间值小只能说明我们需要找这个线段左儿子也就是节点为root＊2
        else if(left>mid)return query(temp+1,left,right);//反之就是root＊2＋1
        else return query(temp,left,mid)+query(temp+1,mid+1,right);//表示当这个节点处于双向都戒不到的情况我们可以知道这个线段应该是分布在左儿子线段的部分和右儿子线段的部分上面只需要人为分为两段然后想加就ok
    }

    void update(int root ,int sum){
        root=record[root];//record数组存放的是对于下标元素在线段树的节点位置
        s1[root].sum+=sum;//找到后就当前节点加上sum
        while(root>>=1) s1[root].sum+=sum;//然后循环到找他的父亲节点，很简单就是不断更行root/2节点的数值
    }

}st;

int main(){
    int t,n,idx;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>aa[i];//将数组存入数组中
        st.build_tree(1,1,n);//重构线段树1,1,n分别的意思为将开始节点定为1，然后1为这个线段树开始节点的left，n为开始节点的right
        string str;
        int x,y;
        cout<<"Case "<<++idx<<":"<<endl;
        while(cin>>str&&str!="End"){
            cin>>x>>y;
            if(str=="Query") cout<<st.query(1,x,y)<<endl;//从1开始是因为我们创建的线段树是1开头的开始遍历我们的线段树找数值
            else if(str=="Add") st.update(x,y);//也就是我们只需要更新下标x出元素在节点中的sum数值，同时还需要将他的父节点更新
            else st.update(x,-y);
        }
    }
    return 0;
}

这篇关于A - 单点修改区间查询 C++的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！