2020-09-23树状数组

http://icpc.upc.edu.cn/problem.php?cid=2586&pid=3

题目描述

We define B(x) as the number of digit 1 in the binary representation of x. For example, B(7) =B((111) 2 ) = 3, B(8) = B((1000) 2 ) = 1, B(9) = B((1001) 2 ) = 2. We define F(x) = min{y j (y > x)∧(B(y)≤B(x))}. For example, F(4) = 8, F(5) = 6, F(6) = 8. Zayin has a forest (a set of trees), whose nodes are numbered from 1 to n. For each node (e.g. node x),if F(x) is not greater than n, then the father of node x is F(x), else, node x is the root of a tree. We use A [ i ] to denote the number of apples on the node i. Initially, all the A [ i ] (1≤i≤n) are equal to zero. In order to make his girlfriend happy, Zayin is going to perform magic on the tree. The magic consists of two types of operations: 1. Add x v : For every ancestor of node x (including itself), put v more apples on it. In other words, for every node (e.g. node y) on the path between node x and the root of its tree, let A[y] = A[y] + v. 2. Sum L R : Count the total number of apples on the nodes whose index is between L and R. In other words, you need to calculate .

输入

The first line contains two integers n and m (1≤n≤1018 , 1≤m≤105 ), where n is the number of nodes and m is the number of operations. The next m lines describe the m operations in order. Each line contains three integers. The first of them is op. If op = 1, then the next two integers will be x and v, representing an Add operation. If op = 2, then the next two integers will be L and R, representing a Sum operation. (1≤x≤n, 1≤v≤109 , 1≤L≤R≤n)

输出

For each Sum operation, output one line including one number, denoting the corresponding result.

样例输入

8 6
1 1 1
1 3 2
1 5 3
1 7 4
2 1 5
2 4 8

样例输出

10
23

树状数组

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast","uroll-loops","omit-frame-pointer","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
unordered_map<ll,ll>w;
void add(ll k,ll m)
{
    for(ll d=m,i=k;i<=n;i+=i&(-i),d+=m)
        w[i]+=d;
}
ll query(ll n)
{
    ll sum=0;
    for(ll i=n;i;i-=i&(-i))
        if(w.count(i))
            sum+=w[i];
    return sum;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int k;
    cin>>n>>k;
    ll a,b,c;
    for(int i=1;i<=k;i++)
    {
        cin>>a>>b>>c;
        if(a==1)
        {
            add(b,c);
        }
        else
        {
            printf("%lld\n",-query(b-1)+query(c));
        }
    }
}