bit.cpp (6)

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