BIT có hàm lower_bound tìm số i nhỏ nhất sao cho get(1,i)>=X
Bài toán
Với một dãy số, thực hiện các truy vấn:
u X Y : tăng phần tử thứ X lên Y đơn vị
g X Y : tính tổng các phần tử từ X đến Y
f X : tìm số i nhỏ nhất sao cho get(1,i) >= X
Độ phức tạp
update: O(logn)
get: O(logn)
find: O(logn)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <stdlib.h>
#define long long long
#define SetLength(a, n, type) a = (type*) calloc(n, sizeof (type))
struct indexed_tree {
int n, logn;
long * T;
void clear(int N){
n=1, logn=0;
while (n<N) { n*=2; logn++; }
SetLength(T, n+1, long);
}
void update(int pos, int value){
for (int i=pos; i<=n; i+=i&-i)
T[i]+=value;
}
long get(int pos){
long r=0;
for (int i=pos; i>=1; i-=i&-i)
r += T[i];
return r;
}
long get(int ll, int rr){
return get(rr)-get(ll-1);
}
int lower_bound(int node, int level, long value){
for (int i=level-1; i>=0; i--)
if (T[node-(1<<i)]>=value)
return lower_bound(node-(1<<i), i, value);
else value-=T[i];
return node;
}
int lower_bound(long value){
if (value>T[n]) return 0;
else return lower_bound(n, logn, value);
}
};
int n, m;
indexed_tree tr;
main(){
char c; int i, x, y;
scanf("%d%d", &n, &m);
tr.clear(n);
for (i=1; i<=m; i++){
scanf(" %c", &c);
if (c=='u' || c=='g') scanf("%d%d", &x, &y);
else if (c=='f') scanf("%d", &x);
if (c=='u') tr.update(x, y);
if (c=='g') printf("%lld\n", tr.get(x, y));
if (c=='f') printf("%d\n", tr.lower_bound(x));
}
}
Nhận xét