verify/yosupo/data-structure/point_add_range_sum.test.cpp
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include "template.hpp"
#include "data-structure/fenwick-tree.hpp"
int main (){
cin . tie ( nullptr ) -> sync_with_stdio ( false );
int n , q ;
cin >> n >> q ;
vector < int > a ( n );
for ( auto & x : a ) cin >> x ;
Fenwick < ll > f ( a );
while ( q -- ){
int op ;
cin >> op ;
if ( op ){
int l , r ;
cin >> l >> r ;
cout << f . query ( l , r - 1 ) << " \n " ;
} else {
int p , x ;
cin >> p >> x ;
f . update ( p , x );
}
}
}
#line 1 "verify/yosupo/data-structure/point_add_range_sum.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#line 2 "template.hpp"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std ;
using namespace __gnu_pbds ;
using ll = long long ;
using db = long double ;
using vi = vector < int > ;
using vl = vector < ll > ;
using vd = vector < db > ;
using pii = pair < int , int > ;
using pll = pair < ll , ll > ;
using pdd = pair < db , db > ;
const int INF = INT_MAX / 2 ;
const int MOD = 998244353 ;
const int MOD2 = 1000000007 ;
const ll LINF = LLONG_MAX / 2 ;
const db DINF = numeric_limits < db >:: infinity ();
const db EPS = 1e-9 ;
const db PI = acos ( db ( - 1 ));
template < class T >
using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update > ;
template < class T >
using ordered_multiset = tree < T , null_type , less_equal < T > , rb_tree_tag , tree_order_statistics_node_update > ;
mt19937 rng ( chrono :: steady_clock :: now (). time_since_epoch (). count ());
mt19937_64 rng64 ( chrono :: steady_clock :: now (). time_since_epoch (). count ());
#line 2 "data-structure/fenwick-tree.hpp"
/**
* Author: Teetat T.
* Date: 2024-01-15
* Description: Fenwick / Binary Indexed Tree
*/
template < class T >
struct Fenwick {
int n , logn ;
vector < T > t ;
Fenwick (){}
Fenwick ( int _n ){ init ( vector < T > ( _n , T {}));}
template < class U >
Fenwick ( const vector < U > & a ){ init ( a );}
template < class U >
void init ( const vector < U > & a ){
n = ( int ) a . size ();
logn = 31 - __builtin_clz ( n );
t . assign ( n + 1 , T {});
for ( int i = 1 ; i <= n ; i ++ ){
t [ i ] = t [ i ] + a [ i - 1 ];
int j = i + ( i &- i );
if ( j <= n ) t [ j ] = t [ j ] + t [ i ];
}
}
void update ( int x , const T & v ){
for ( int i = x + 1 ; i <= n ; i += i &- i ) t [ i ] = t [ i ] + v ;
}
void update ( int l , int r , const T & v ){
update ( l , v ), update ( r + 1 , - v );
}
T query ( int x ){
T res {};
for ( int i = x + 1 ; i > 0 ; i -= i &- i ) res = res + t [ i ];
return res ;
}
T query ( int l , int r ){
return query ( r ) - query ( l - 1 );
}
int find ( const T & k ){
int x = 0 ;
T cur {};
for ( int i = 1 << logn ; i > 0 ; i >>= 1 )
if ( x + i <= n && cur + t [ x + i ] <= k ) x += i , cur = cur + t [ x ];
return x ;
}
};
#line 4 "verify/yosupo/data-structure/point_add_range_sum.test.cpp"
int main (){
cin . tie ( nullptr ) -> sync_with_stdio ( false );
int n , q ;
cin >> n >> q ;
vector < int > a ( n );
for ( auto & x : a ) cin >> x ;
Fenwick < ll > f ( a );
while ( q -- ){
int op ;
cin >> op ;
if ( op ){
int l , r ;
cin >> l >> r ;
cout << f . query ( l , r - 1 ) << " \n " ;
} else {
int p , x ;
cin >> p >> x ;
f . update ( p , x );
}
}
}
Back to top page