Ronzii's Blog

Just your average geek's blog

Binary Indexed Tree

Topcoder is a great resource for understanding it. See here.

#include <iostream>
#include <cstring>
using namespace std;
class bit
{
    int *tree;
    int maxVal;
public:
    bit(int N)
    {
        tree = new int[N+1];
        memset(tree,0,sizeof(int)*(N+1));
        maxVal = N;
    }
    void update(int idx, int val)
    {
        while (idx <= maxVal)
        {
            tree[idx] += val;
            idx += (idx & -idx);
        }
    }
    int read(int idx)
    {
        int sum=0;
        while (idx>0)
        {
            sum += tree[idx];
            idx -= (idx & -idx);
        }
        return sum;
    }
    int readSingle(int idx)
    {
        int sum = tree[idx];
        if (idx > 0)
        {
            int z = idx - (idx & -idx);
            idx--;
            while(idx!=z)
            {
                sum-=tree[idx];
                idx-=(idx & -idx);
            }
        }
        return sum;
    }
};

int main()
{
    int a[] = {1,0,2,1,1,3,0,4,2,5,2,2,3,1,0,2};
    int n = sizeof(a)/sizeof(a[0]),MAX=65536,x;
    bit v(MAX);
    for(int i=1; i<=n; i++)
        v.update(i,a[i-1]);
    while (cin>>x)
        cout<<v.read(x)<<endl;
    return 0;
}

March 20, 2012 Posted by | C++ | , , , | Leave a comment

Generalized Summation

Write an algorithm to find out how many different summations you can compute using numbers range from 1 to 1000. 2 constraints
1) Each valid sum must be less than 10000
2) A number can only be used once for a sum
example:
1+2+300 < 10000 is valid
1+2+300+400 < 10000 is valid
1+2+2 is not valid (2 appear twice)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int summation(vector<int> v,int maxSumAllowed)
{
    int n = v.size();
    int sum = accumulate(v.begin(),v.end(),0);
    int *s = new int[sum+1];
    s[0] = 1;
    for(int i=1; i<=sum; i++) s[i] = 0;
    int R = 0;
    for(int i=0; i<n; i++)
    {
        for(int j = R; j>=0; j--)
        {
            if(s[j] && j+v[i]<maxSumAllowed)
            {
                s[j+v[i]]+=1;
            }
        }
        R = max(sum/2,R+s[i]);
    }
    int result = 0;
    for(int i=0; i<=maxSumAllowed; i++) result+=s[i];
    return result;
}
int main()
{
    int n = 4;
    vector<int> v;
    for(int i=1; i<=n; i++)
    {
        v.push_back(i);
    }
    cout<<summation(v,4);
    return 0;
}

 

March 20, 2012 Posted by | C++, Dynamic Programming | , , , , , , , | Leave a comment