Fenwick Tree – Live with passion

11610

Asif NaeemOctober 19, 2015

To solve the problem indexes of the array are also needed to be updated and queried.

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

struct RevPrime{
	int reversePrime;
	int factorCount;
};

int prime[1000001];
RevPrime arr[80000];
int Bit[2][80000];

vector<int> vb;
int k=1;

int reverse(int a)
{
	int num=0;
	while(a)
	{
		num*=10;
		num += (a%10);
		a/=10;
	}
	return num;
}

bool cmp(RevPrime a,RevPrime b)
{
	return a.reversePrime<b.reversePrime;
}

void update(int row,int idx,int val)
{
	while(idx<k)
	{
		Bit[row][idx]+=val;
		idx +=(idx & (-idx));
	}
}

int query(int row,int idx)
{
	int ret=0;
	while(idx>0)
	{
		ret+=Bit[row][idx];
		idx -= (idx & (-idx));
	}
	return ret;
}

int binarySearch(int lw,int hi,int val)
{
	if(hi<lw)
		return 0;
	int mid = (hi+lw)>>1;
	if(arr[mid].reversePrime<val)
	{
		return binarySearch(mid+1,hi,val);
	}
	else if(arr[mid].reversePrime>val)
	{
		return binarySearch(lw,mid,val);
	}
	else if(arr[mid].reversePrime==val)
		return mid;
	return 0;
}

int findIndex_bianarySearch(int lw,int hi,int modifiedIndex_value)
{
	if(hi<lw)
		return 0;
	int mid =(hi+lw)>>1;
	int mid_val=query(1,mid);
	if(mid_val<modifiedIndex_value)
		return findIndex_bianarySearch(mid+1,hi,modifiedIndex_value);
	else if(mid_val>modifiedIndex_value)
		return findIndex_bianarySearch(lw,mid,modifiedIndex_value);
	else
		return mid;
	return 0;
}

int main () {
    int b;
	int tmp;
    for(int i=2;i<1000001;i++)
    {
    	if(prime[i]==0)
    	{
    		prime[i]+=1;
    		vb.push_back(i);
    		for(int j=i+i;j<1000001;j+=i)
    		{
    			prime[j]+=1;
    			tmp=j/i;
    			while(tmp%i==0)
    			{
    				prime[j]+=1;
    				tmp/=i;
    			}
    		}
    	}
    }
    for(int i=0;i<vb.size();i++)
    {
    	b = reverse(vb[i]);
    	arr[k].factorCount=prime[b];
    	while(b<1000000)
    	{
    		b*=10;
    		arr[k].factorCount+=2;
    	}
    	arr[k].reversePrime=b;
    	k+=1;
    }
    sort(arr,arr+k,cmp);
    for(int i=1;i<k;i++)
    {
		update(0,i,arr[i].factorCount);
		update(1,i,1);
	}
    char ch;
    int n;
    while(scanf("%c", &ch)!=EOF)
    {
    	scanf("%d",&n);
    	if(ch=='q')
    	{
			int original_index=findIndex_bianarySearch(1,k,n+1);
    		cout<<query(0,original_index)<<"\n";
    	}
    	if(ch=='d')
    	{
    		int idx = binarySearch(1,k,n);
    		update(0,idx,(-1)*arr[idx].factorCount);
			update(1,idx,-1);

    	}
    }
    return 0;
}

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

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

struct RevPrime{

int reversePrime;

int factorCount;

};

int prime[1000001];

RevPrime arr[80000];

int Bit[2][80000];

vector<int> vb;

int k=1;

int reverse(int a)

{

int num=0;

while(a)

{

num*=10;

num += (a%10);

a/=10;

}

return num;

}

bool cmp(RevPrime a,RevPrime b)

{

return a.reversePrime<b.reversePrime;

}

void update(int row,int idx,int val)

{

while(idx<k)

{

Bit[row][idx]+=val;

idx +=(idx & (-idx));

}

int query(int row,int idx)

{

int ret=0;

while(idx>0)

{

ret+=Bit[row][idx];

idx -= (idx & (-idx));

}

return ret;

}

int binarySearch(int lw,int hi,int val)

{

if(hi<lw)

return 0;

int mid = (hi+lw)>>1;

if(arr[mid].reversePrime<val)

{

return binarySearch(mid+1,hi,val);

}

else if(arr[mid].reversePrime>val)

{

return binarySearch(lw,mid,val);

}

else if(arr[mid].reversePrime==val)

return mid;

return 0;

}

int findIndex_bianarySearch(int lw,int hi,int modifiedIndex_value)

{

if(hi<lw)

return 0;

int mid =(hi+lw)>>1;

int mid_val=query(1,mid);

if(mid_val<modifiedIndex_value)

return findIndex_bianarySearch(mid+1,hi,modifiedIndex_value);

else if(mid_val>modifiedIndex_value)

return findIndex_bianarySearch(lw,mid,modifiedIndex_value);

else

return mid;

return 0;

}

int main () {

int b;

int tmp;

for(int i=2;i<1000001;i++)

{

if(prime[i]==0)

{

prime[i]+=1;

vb.push_back(i);

for(int j=i+i;j<1000001;j+=i)

{

prime[j]+=1;

tmp=j/i;

while(tmp%i==0)

{

prime[j]+=1;

tmp/=i;

}

for(int i=0;i<vb.size();i++)

{

b = reverse(vb[i]);

arr[k].factorCount=prime[b];

while(b<1000000)

{

b*=10;

arr[k].factorCount+=2;

}

arr[k].reversePrime=b;

k+=1;

}

sort(arr,arr+k,cmp);

for(int i=1;i<k;i++)

{

update(0,i,arr[i].factorCount);

update(1,i,1);

}

char ch;

int n;

while(scanf("%c", &ch)!=EOF)

{

scanf("%d",&n);

if(ch=='q')

{

int original_index=findIndex_bianarySearch(1,k,n+1);

cout<<query(0,original_index)<<"\n";

}

if(ch=='d')

{

int idx = binarySearch(1,k,n);

update(0,idx,(-1)*arr[idx].factorCount);

update(1,idx,-1);

}

return 0;

}

10666

Asif NaeemOctober 18, 2015

#include <iostream>
#include <cstdio>

using namespace std;
//no of 1' indicate how many times at least it lost a game
//no of 0' indicate how many times at least it lost a game
//so if a team id does not contain a 0 it can be the last of the tournament at it pessimist decision
int NoOfRounds;
int TeamNo;
int TwosPower[31];

int main()
{
	int t;
	int countOne;
	int countZero;
	scanf("%d",&t);
	TwosPower[0]=1;
	for(int i=1;i<31;i++)
		TwosPower[i]=TwosPower[i-1]<<1;
	while(t--)
	{
		scanf("%d%d",&NoOfRounds,&TeamNo);
		int tmp = TeamNo;
		countOne=0;
		while(tmp)
		{
			if(tmp%2)
			countOne+=1;
			tmp = tmp>>1;
		}
		//to find the worst case : after the first lost rest of the game can be considered as lost
		//so find the the first lost=first 1 from the left
		//from this we can find least number of winning match
		//subtract this from total number of matches of that tournaments.
		//each zero from the left means the team is better than the rest of the players of that round.
		tmp = TeamNo;
		countZero=0;
		int i=0;
		while(i<NoOfRounds)
		{
			if(tmp%2)
			break;
			else
			countZero+=TwosPower[i++];
			tmp=tmp>>1;
		}
		printf("%d %d\n",countOne+1,TwosPower[NoOfRounds]-countZero);
	}
	return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

//no of 1' indicate how many times at least it lost a game

//no of 0' indicate how many times at least it lost a game

//so if a team id does not contain a 0 it can be the last of the tournament at it pessimist decision

int NoOfRounds;

int TeamNo;

int TwosPower[31];

int main()

{

int t;

int countOne;

int countZero;

scanf("%d",&t);

TwosPower[0]=1;

for(int i=1;i<31;i++)

TwosPower[i]=TwosPower[i-1]<<1;

while(t--)

{

scanf("%d%d",&NoOfRounds,&TeamNo);

int tmp = TeamNo;

countOne=0;

while(tmp)

{

if(tmp%2)

countOne+=1;

tmp = tmp>>1;

}

//to find the worst case : after the first lost rest of the game can be considered as lost

//so find the the first lost=first 1 from the left

//from this we can find least number of winning match

//subtract this from total number of matches of that tournaments.

//each zero from the left means the team is better than the rest of the players of that round.

tmp = TeamNo;

countZero=0;

int i=0;

while(i<NoOfRounds)

{

if(tmp%2)

break;

else

countZero+=TwosPower[i++];

tmp=tmp>>1;

}

printf("%d %d\n",countOne+1,TwosPower[NoOfRounds]-countZero);

}

return 0;

}

1428

Asif NaeemOctober 17, 2015

The problem can be solved using Binary Indexed tree or Fenwick tree.

#include <cstdio>
#include <queue>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>

#define SZ 100000+5
#define ll long long

using namespace std;

int arr[SZ];
ll Left[SZ],Right[SZ],sum[SZ];
int mx;

ll Cumulative(int idx)
{
	ll value=0;
	while(idx>0)
	{
		value += sum[idx];
		idx -= (idx & (-idx));
	}
	return value;
}

void update(int idx)
{
	while(idx<=mx)
	{
		sum[idx]+=1;
		idx += (idx & (-idx));
	}
}
int main()
{
	int t,N;
	ll ans;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&N);
		mx=-1;
		for(int i=1;i<=N;i++)
		{
			scanf("%d",&arr[i]);
			if(mx<arr[i])
			mx=arr[i];
		}
		memset(Left,0,sizeof(Left));
		memset(Right,0,sizeof(Right));
		memset(sum,0,sizeof(sum));

		for(int i=1;i<=N;i++)
		{
			Left[i]=Cumulative(arr[i]);//finds the number of smaller number than arr[i] to its Left
			update(arr[i]);
		}
		memset(sum,0,sizeof(sum));
		for(int i=N;i>=1;i--)
		{
			Right[i]=Cumulative(arr[i]);
			update(arr[i]);
			//ans += Left[i]*(N-)
		}
		ans = 0;
		for(int i=N;i>=1;i--)
		{
			ans += Left[i]*(N-i-Right[i]) + Right[i]*(i-1-Left[i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

#include <cstdio>

#include <queue>

#include <vector>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <string>

#define SZ 100000+5

#define ll long long

using namespace std;

int arr[SZ];

ll Left[SZ],Right[SZ],sum[SZ];

int mx;

ll Cumulative(int idx)

{

ll value=0;

while(idx>0)

{

value += sum[idx];

idx -= (idx & (-idx));

}

return value;

}

void update(int idx)

{

while(idx<=mx)

{

sum[idx]+=1;

idx += (idx & (-idx));

}

int main()

{

int t,N;

ll ans;

scanf("%d",&t);

while(t--)

{

scanf("%d",&N);

mx=-1;

for(int i=1;i<=N;i++)

{

scanf("%d",&arr[i]);

if(mx<arr[i])

mx=arr[i];

}

memset(Left,0,sizeof(Left));

memset(Right,0,sizeof(Right));

memset(sum,0,sizeof(sum));

for(int i=1;i<=N;i++)

{

Left[i]=Cumulative(arr[i]);//finds the number of smaller number than arr[i] to its Left

update(arr[i]);

}

memset(sum,0,sizeof(sum));

for(int i=N;i>=1;i--)

{

Right[i]=Cumulative(arr[i]);

update(arr[i]);

//ans += Left[i]*(N-)

}

ans = 0;

for(int i=N;i>=1;i--)

{

ans += Left[i]*(N-i-Right[i]) + Right[i]*(i-1-Left[i]);

}

printf("%lld\n",ans);

}

return 0;

}

To know something More. From the above source:

Let's take the first example - 3, 1, 2. At the beginning the BIT is 0, 0, 0. After inserting 3 the BIT is 0, 0, 1. After inserting 1 the BIT is 1, 0, 1 which gives 1 inversion. After inserting 2, the BIT is 1, 1, 1 which gives again 1 inversion. 1 + 1 = 2 total inversions.

Let's take the second example - 2, 3, 8, 6, 1.
BIT - 0, 0, 0, 0, 0, 0, 0, 0. Insert 2:
BIT - 0, 1, 0, 0, 0, 0, 0, 0. Insert 3:
BIT - 0, 1, 1, 0, 0, 0, 0, 0. Insert 8:
BIT - 0, 1, 1, 0, 0, 0, 0, 1. Insert 6: +1 inversions
BIT - 0, 1, 1, 0, 0, 1, 0, 1. Insert 1: + 4 inversions
BIT - 1, 1, 1, 0, 0, 1, 0, 1.

P.S. In the examples I haven't included the compression for clarity.

Let's take the first example - 3, 1, 2. At the beginning the BIT is 0, 0, 0. After inserting 3 the BIT is 0, 0, 1. After inserting 1 the BIT is 1, 0, 1 which gives 1 inversion. After inserting 2, the BIT is 1, 1, 1 which gives again 1 inversion. 1 + 1 = 2 total inversions.

Let's take the second example - 2, 3, 8, 6, 1.

BIT - 0, 0, 0, 0, 0, 0, 0, 0. Insert 2:

BIT - 0, 1, 0, 0, 0, 0, 0, 0. Insert 3:

BIT - 0, 1, 1, 0, 0, 0, 0, 0. Insert 8:

BIT - 0, 1, 1, 0, 0, 0, 0, 1. Insert 6: +1 inversions

BIT - 0, 1, 1, 0, 0, 1, 0, 1. Insert 1: + 4 inversions

BIT - 1, 1, 1, 0, 0, 1, 0, 1.

P.S. In the examples I haven't included the compression for clarity.

Sample code implementing the binary indexed tree data structure to find the # of smaller numbers than a number of an array.

#include<iostream>

using namespace std;

int ftree[10000001]={0};

int cum(int idx){
	int result=0;
	while(idx>0){
		result=result+ftree[idx];
		idx=idx-(idx & -idx);
	}

	return result;
}

void update(int idx,int val){
	while(idx<=10000000){
		ftree[idx]=ftree[idx]+val;
		idx=idx+(idx & -idx);
	}
}

int main()
{
	int t;
	cin>>t;
	for(int w=0;w<t;w++){
		int n;
		cin>>n;
		int ele;
		long int count=0;
		for(int i=0;i<n;i++){
			cin>>ele;
			update(ele,1);
			count=count+cum(10000000)-cum(ele);
		}
		cout<<count<<"\n";
		for(int i=1;i<=10000000;i++)
			ftree[i]=0;
	}
	return 0;
}

#include<iostream>

using namespace std;

int ftree[10000001]={0};

int cum(int idx){

int result=0;

while(idx>0){

result=result+ftree[idx];

idx=idx-(idx & -idx);

}

return result;

}

void update(int idx,int val){

while(idx<=10000000){

ftree[idx]=ftree[idx]+val;

idx=idx+(idx & -idx);

}

int main()

{

int t;

cin>>t;

for(int w=0;w<t;w++){

int n;

cin>>n;

int ele;

long int count=0;

for(int i=0;i<n;i++){

cin>>ele;

update(ele,1);

count=count+cum(10000000)-cum(ele);

}

cout<<count<<"\n";

for(int i=1;i<=10000000;i++)

ftree[i]=0;

}

return 0;

}

12532

Asif NaeemNovember 18, 2014

/*****Binary Index tree  12532******/
#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>

#define SZ 100005
#define ll long long

using namespace std;

int num[SZ];
int neg[SZ];
int zero[SZ];
int maxInd;

void update(int *arr,int ind,int val)
{
	while(ind<maxInd)
	{
		arr[ind]+=val;
		ind+=(ind & (-ind));
	}
}


int read(int *arr,int ind)
{
	int res =0;
	while(ind>0)
	{
		res+=arr[ind];
		ind-=(ind & (-ind));
	}
	return res;
}

int main()
{
	int a,n,k;
	string s;
	char ch;
	int valu,idx;
	while(cin>>n)
	{
		cin>>k;
		memset(zero,0,sizeof(zero));
		memset(neg,0,sizeof(neg));

		maxInd =n+1;
		for(int i=1;i<=n;i++)
		{
			cin>>a;
			if(a<0)
			{
				update(neg,i,1);
			}
			else if(a==0)
			{
				update(zero,i,1);
			}
			num[i]=a;
		}
		s="";
		//cout<<n<<" "<<k<<"\n";
		while(k--)
		{
			cin>>ch>>idx>>valu;

			if(ch=='C')
			{
				if(valu<0)
				{
					if(num[idx]==0)
					{
						update(zero,idx,-1);
						update(neg,idx,1);
					}
					else if(num[idx]>0)
					{
						update(neg,idx,1);
					}
				}
				else if(valu==0)
				{
					if(num[idx]>0)
					{
						update(zero,idx,1);
					}
					else if(num[idx]<0)
					{
						update(zero,idx,1);
						update(neg,idx,-1);
					}
				}
				else if(valu>0)
				{
					if(num[idx]==0)
					{
						update(zero,idx,-1);
					}
					else if(num[idx]<0)
					{
						update(neg,idx,-1);
					}
				}

				num[idx] = valu;
			}//end command type check

			else if(ch=='P')
			{
				int d,m;
				d = read(zero,valu) - read(zero,idx-1);
				m = read(neg,valu) - read(neg,idx-1);
				//cout<<"dm = "<<d<<" "<<m<<"\n";
				if(d>0)
				{
					s.append(1u,'0');
					//cout<<"0";
				}
				else if(m%2==1)
				{
					s.append(1u,'-');
					//cout<<"-";
				}
				else if(d==0 && (m%2)==0)
					s.append(1u,'+');
					//cout<<"+";

			}
		}
		cout<<s<<"\n";
	}

	return 0;
}

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

127

128

129

130

131

132

133

134

135

136

137

138

/*****Binary Index tree 12532******/

#include <stdio.h>

#include <iostream>

#include <string>

#include <string.h>

#include <math.h>

#define SZ 100005

#define ll long long

using namespace std;

int num[SZ];

int neg[SZ];

int zero[SZ];

int maxInd;

void update(int *arr,int ind,int val)

{

while(ind<maxInd)

{

arr[ind]+=val;

ind+=(ind & (-ind));

}

int read(int *arr,int ind)

{

int res =0;

while(ind>0)

{

res+=arr[ind];

ind-=(ind & (-ind));

}

return res;

}

int main()

{

int a,n,k;

string s;

char ch;

int valu,idx;

while(cin>>n)

{

cin>>k;

memset(zero,0,sizeof(zero));

memset(neg,0,sizeof(neg));

maxInd =n+1;

for(int i=1;i<=n;i++)

{

cin>>a;

if(a<0)

{

update(neg,i,1);

}

else if(a==0)

{

update(zero,i,1);

}

num[i]=a;

}

s="";

//cout<<n<<" "<<k<<"\n";

while(k--)

{

cin>>ch>>idx>>valu;

if(ch=='C')

{

if(valu<0)

{

if(num[idx]==0)

{

update(zero,idx,-1);

update(neg,idx,1);

}

else if(num[idx]>0)

{

update(neg,idx,1);

}

else if(valu==0)

{

if(num[idx]>0)

{

update(zero,idx,1);

}

else if(num[idx]<0)

{

update(zero,idx,1);

update(neg,idx,-1);

}

else if(valu>0)

{

if(num[idx]==0)

{

update(zero,idx,-1);

}

else if(num[idx]<0)

{

update(neg,idx,-1);

}

num[idx] = valu;

}//end command type check

else if(ch=='P')

{

int d,m;

d = read(zero,valu) - read(zero,idx-1);

m = read(neg,valu) - read(neg,idx-1);

//cout<<"dm = "<<d<<" "<<m<<"\n";

if(d>0)

{

s.append(1u,'0');

//cout<<"0";

}

else if(m%2==1)

{

s.append(1u,'-');

//cout<<"-";

}

else if(d==0 && (m%2)==0)

s.append(1u,'+');

//cout<<"+";

}

cout<<s<<"\n";

}

return 0;

}

Category: Fenwick Tree

11610

10666

1428

12532

Archives

Categories