সোমবার, ২১ ডিসেম্বর, ২০১৫

BIT / Fenwick tree An implementation 


  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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <bits/stdc++.h>
#define garbazeVal -1
using namespace std;
int freq[100007] = {garbazeVal,3,4,0,12,4,5,23,45,23,35};
//How many students got 0,1,2,3,...............
//How many students got A+,A-,B+,B-,.......
//Map : sort according to some criteria
// A+ -> 1
// A  -> 2
// A- -> 3 (new indexes)
//For numerical - s we can do shifting
//minimum - 1000 ,so every index is now
// previous value + 1001
//-80  -> 921 [new index]
int Fentree[100007];
int query(int idx)
{
//Query 0 is not handled
    /*

    If it was , Then
                      if(idx==0)
                          return freq[0];
    */
    /*
    If 0 was included in the range
    then we d do just do this ,

    sum+=freq[0] ;


    ....
    ....

    return sum;

    */
    int sum=0;

    while(idx>0)
    {
        cout<<"Now at index "<<idx<<endl;
        sum+=Fentree[idx];
        idx -= idx & (-idx);
        cout<<"Sum is "<<sum<<endl;
    }
    return sum;

}
void update(int i,int v)
{
    //index 0 is untouched
    while(i<=10)
    {
        Fentree[i]+=v;
        i+=(i&(-i));
    }
}
void constr()
{
    for(int a=1; a<=10; a++)
    {
        update(a,freq[a]);
    }
}
int main()
{
    memset(Fentree,0,sizeof(Fentree));
    constr();

    cout<<"---------UPDATE---------"<<endl;
    for(int x=1; x<=10; x++)
    {
        int tt = x;
        cout<<"For "<<x<<" : ";
        while(tt<=10)
        {
            cout<<"+"<<" "<<tt;
            tt += tt&-tt;

        }
        cout<<endl;
    }

    cout<<"----------QUERY----------"<<endl;

    for(int x=1; x<=10; x++)
    {
        int tt = x;
        cout<<"For "<<x<<" : ";
        while(tt>0)
        {
            cout<<"->+["<<" "<<tt<<" ]";
            tt -= tt&-tt;

        }
        cout<<endl;
    }

//Why we can't use index 0
    cout<< "0 & -0 is just 0.-->"<< (0&(-0)) <<endl;
    cout<<"\nSo,to implement query 0 -> 0+(0&(-0)) -> 0 + 0 -> 0"<<endl;
    cout<<"0 calls 0.0 calls 0...When to stop?.But we could do this ..."<<endl;
    cout<<"if(idx == 0)\n    return freq[0] \n in O(1)"<<endl;
    cout<<"But that would make update function O(n) and ultimately \n" // Why ???
        <<"that would be q*log(n) [query] + u*n [update] for q queries and u updates with n items/buckets"
        <<"\n as for index 1 we updated index 1,2,4,8 [powers of 2]\n"
        <<"To include 0 we had to further update all i from 0 to n.\n";




    cout<<"Or,we could still include 0 and make the complexity q*log(n) + u*log(n)"<<endl;
    cout<<"The idea is that we keep the update function same 1 to n"<<endl;
    cout<<"But in the query function we first add freq[0] to sum and then do the decrementing of index"<<endl;

    while(1)
    {
        cout<<"Query :";
        int q;
        cin>>q;
        query(q);
    }

    return 0;
}
এর দ্বারা পোস্ট করা এই সময়ে

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

এতে সদস্যতা: মন্তব্যগুলি পোস্ট করুন (Atom)