Submission #62003

ソースコード

?
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
//一点更新、区間取得を求めるBIT
#include<bits/stdc++.h>
using namespace std;
struct BinaryIndexedTree{
int N;
vector<long long> bit;
//全て0で初期化
BinaryIndexedTree(int size){
bit.resize(size+1,0);
N=size+1;
}
//bit[a]に値wを加える。O(log n)
void add(int a,long long w){
for(int x=a;x<=N;x+=(x & -x)) bit[x]+=w;
return;
}
//bit[1,a]の和bit[1]+bit[2]+ +bit[a]を求める。 O(log n)
long long sum(long long a){
long long ret=0;
for(int x=a;x>0;x-=(x & -x)) ret+=bit[x];
return ret;
}
};
//動作確認はAOJ DSL 2 B Range Sum Query(RSQ)にて行いました。
int main(){
int n,q;
cin>>n>>q;
BinaryIndexedTree BIT(n+5);
long long com,x,y;
for(int i=0;i<q;i++){
cin>>com>>x>>y;
if(com==0){
BIT.add(x,y);
}
else{
cout<<BIT.sum(y)-BIT.sum(x-1)<<'\n';
}
}
return(0);
}

ステータス

項目 データ
問題 0649 - 区間和(セグ木、BIT練習)
ユーザー名 ei1918
投稿日時 2020-08-13 09:29:42
言語 C++14
状態 Accepted
得点 5
ソースコード長 1028 Byte
最大実行時間 1386 ms
最大メモリ使用量 96232 KB

セット

セット 得点 Cases
1 ALL 5 / 5 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input100-1 AC 101 ms 988 KB
1
input100-2 AC 217 ms 1856 KB
1
input100-3 AC 463 ms 4260 KB
1
input100-4 AC 937 ms 8708 KB
1
input100-5 AC 1386 ms 15972 KB
1
input1000-1 AC 443 ms 18116 KB
1
input1000-2 AC 1019 ms 23072 KB
1
input1000-3 AC 464 ms 25332 KB
1
input1000-4 AC 1250 ms 31692 KB
1
input1000-5 AC 387 ms 33448 KB
1
input10000-1 AC 1158 ms 39300 KB
1
input10000-2 AC 1281 ms 45592 KB
1
input10000-3 AC 1008 ms 50600 KB
1
input10000-4 AC 1160 ms 56124 KB
1
input10000-5 AC 603 ms 58956 KB
1
input100000-1 AC 1347 ms 66140 KB
1
input100000-2 AC 224 ms 66988 KB
1
input100000-3 AC 230 ms 68092 KB
1
input100000-4 AC 697 ms 71376 KB
1
input100000-5 AC 1192 ms 77092 KB
1
input1000000-1 AC 149 ms 84732 KB
1
input1000000-2 AC 497 ms 86744 KB
1
input1000000-3 AC 583 ms 89268 KB
1
input1000000-4 AC 1080 ms 94224 KB
1
input1000000-5 AC 479 ms 96232 KB
1
input1001000-1 AC 18 ms 88640 KB
1
input1001000-2 AC 16 ms 88488 KB
1
input1001000-3 AC 19 ms 88592 KB
1
input1001000-4 AC 19 ms 88556 KB
1
input1001000-5 AC 27 ms 88528 KB
1