Tree Recovery

简介: Tree Recovery

Tree Recovery


题目:


You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.


输入描述:


The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.

The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000.

Each of the next Q lines represents an operation.

"C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000.

"Q a b" means querying the sum of Aa, Aa+1, ... , Ab.


输出描述:


You need to answer all Q commands in order. One answer in a line.


示例1


输入


10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4


输出


4

55

9

15


思路:和上篇差不多,一个经典树状数组稍微变形


#include<bits/stdc++.h>
using namespace std;
long long n,q;
int a[101010];
long long lowbit(long long x)
{
    return x&-x;
}
void add(long long i,long long x)
{
    while(i<=n)
    {
        a[i]+=x;
        i+=lowbit(i);
    }
}
long long sum(long long i)
{
    long long ans=0;
    while(i>0)
    {
        ans+=a[i];
        i-=lowbit(i);
    }
    return ans;
}
int main()
{
    cin>>n>>q;
    long long x,a,b,c;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        add(i,x);
    }
    string s;
    while(q--)
    {
        cin>>s;
        if(s=="Q"){
            cin>>a>>b;
            cout<<sum(b)-sum(a-1)<<endl;
        }
        else{
            cin>>a>>b>>c;
            for(int i=a;i<=b;i++)
            add(i,c);
        }
    }
    return 0;
}

目录
相关文章
|
3月前
crash命令 —— tree
crash命令 —— tree
|
7月前
|
数据库 OceanBase
min restore scn of backup set file is greater than restore scn. can't use to restor
min restore scn of backup set file is greater than restore scn. can't use to restor
50 1
|
机器学习/深度学习
Data Structures (五) - 二叉树Binary Tree
Data Structures (五) - 二叉树Binary Tree
Data Structures (五) - 二叉树Binary Tree
1110. Complete Binary Tree (25)
#include #include #include #include using namespace std; struct node { int ad, l, r; }; vector visited(20, ...
988 0
|
机器学习/深度学习
1064. Complete Binary Search Tree (30)
#include #include #include using namespace std; const int maxn = 1001; vector num(maxn), cbt(maxn); int n, c...
848 0
|
Oracle 关系型数据库 数据库
ORA-01189的完整解决过程(File is from a different RESETLOGS than previous files)
昨天用户报告数据库不能启动了,询问用户,用户也不清楚原因。在解决过程中遇到了ORA-01189的问题,查遍了网上,包括metalink,也没有找到合适的解决方案,差点就放弃了......还好,根据ORACLE的错误解释,终于摸索出了下面的解决方法。
1433 0
|
SQL Oracle 关系型数据库
[LeetCode] Recover Binary Search Tree
As the note in the problem statement, this problem has a straight-forward O(n)-space solution, which is to generate the inorder traversal results of t...
674 0