-
Notifications
You must be signed in to change notification settings - Fork 0
/
segment_tree.cpp
74 lines (67 loc) · 1.38 KB
/
segment_tree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
# define FAST_CODE ios_base::sync_with_stdio(false); cin.tie(NULL);
# define pb push_back
# define f(a, b, jump) for(ll i=a; i<=b; i+=jump)
using namespace std;
constexpr ll n = 4e6;
ll tree[n+1];
void build(ll a[], ll node, ll L, ll R)
{
if (L == R)
{
tree[node] = a[L];
}
else
{
ll M = (L + R)/2;
build(a, node*2, L, M);
build(a, node*2+1, M+1, R);
tree[node] = tree[node*2] + tree[node*2+1];
}
}
ll query(ll node, ll L, ll R, ll l, ll r)
{
if (l > r)
return 0;
if (l == L && r == R)
{
return tree[node];
}
ll M = (L + R) / 2;
return query(node*2, L, M, l, min(r, M)) + query(node*2+1, M+1, R, max(l, M+1), r);
}
void update(ll node, ll L, ll R, ll pos, ll new_val)
{
if (L == R)
{
tree[node] = new_val;
}
else
{
ll M = (L + R) / 2;
if (pos <= M)
update(node*2, L, M, pos, new_val);
else
update(node*2+1, M+1, R, pos, new_val);
tree[node] = tree[node*2] + tree[node*2+1];
}
}
int main()
{
FAST_CODE;
// ld a = 7;
// ld b = 3;
// ld x = b/a;
// cout << setprecision(6)<< fixed<<ld(x);
ll n;
cin>>n;
ll a[n];
f(0, (n-1), 1) cin>>a[i];
build(a, 1, 0, 6);
cout<<query(1, 0, n-1, 1, 3)<<endl;
update(1, 0, n-1, 2, 10);
cout<<query(1, 0, n-1, 1, 3);
return 0;
}