BIT(binary index tree)

UPDATEIT - Update the array +(range update point query !!!!)

BIT RANGE UPDATE AND POINT QUERY !!!!

Given an array A of N numbers, we need to support adding a value v to each element A[a…b] and querying the value of A[p], both operations in O(log N). Let ft[N+1] denote the underlying fenwick tree.

# Add v to A[p]
update(p, v):
  for (; p <= N; p += p&(-p))
    ft[p] += v   

# Add v to A[a...b] 
update(a, b, v):     
  update(a, v)     
  update(b + 1, -v)    

# Return A[b]  
query(b):     
  sum = 0     
  for(; b > 0; b -= b&(-b))
    sum += ft[b]
  return sum

view raw Range Updates and Point Queries.py hosted with

by GitHub

Explanation: update(p, v) will affect all p’ >= p. To limit the effect to a given range [a…b], we subtract -v from all p’ > b by performing the operation update(b+1, -v).

--------------------------------------------spoj updateit-------------------------------------------------------------------------------

http://www.spoj.com/problems/UPDATEIT/

UPDATEIT - Update the array

You have an array containing n elements initially all 0. You need to do a number of update operations on it. In each update you specify l, r and val which are the starting index, ending index and value to be added. After each update, you add the 'val' to all elements from index l to r. After 'u' updates are over, there will be q queries each containing an index for which you have to print the element at that index.

Input

First line consists of t, the number of test cases. (1<=t<=10)

Each test case consists of "n u",number of elements in the array and the number of update operations, in the first line (1<=n<=10000 and 1<=u<=100000)

Then follow u lines each of the format "l r val" (0<=l,r<n 0<=val<=10000)

Next line contains q, the number of queries. (1<=q<=10000)

Next q lines contain an index (0<=index<n)

Output

For each test case, output the answers to the corresponding queries in separate lines.

Example

Input:
1
5 3
0 1 7
2 4 6
1 3 2
3
0
3
4

Output

-----------------------------code-------------------------------------------------------------------

#include<iostream>
using namespace std;
#include<bits/stdc++.h>
typedef long long int lli;
lli  arr[10000000];
lli tree[1000000];
   int n;
   

  
 
 // increase ith index value by val ..
 void update(int val,int index)
  {
   while(index<=n)
   {
      tree[index]+=val;
    index+=index & (-index);
    
   }
  }
  
  // sum from index 1 to index 
  lli  query(int index)
    {
    // cout<<"query till "<<index<<endl;
     
     lli sum=0;
      while(index!=0)
       {
        sum+=tree[index];
        index-=index & (-index);
    }
    return sum;
 }
 
 
 int main()
  {
    int test ;
    cin>>test;
    while(test--)
     {
      
      for(int i=0;i<100001;i++)  tree[i]=0;
  int u;
     cin>>n>>u;

/// fist update query 
      while(u--)
       {
      lli  l,r,v;
          scanf("%lld %lld %lld",&l,&r,&v);
          l+=1;
          r+=1;
          update(v,l);
          update(-v,r+1);
    }
    
 
     int q;
      cin>>q;
      while(q--)
       {
         int  a,b;
          scanf("%d",&a);
          a+=1;
          b+=1;
           printf("%lld\n",query(a));
        
  }
 }
  return 0;
   
  }

BIT-- POINT UPDATE AND RANGE QUERY !!!!

BIT-- POINT UPDATE AND RANGE QUERY !!!!

#include<iostream>
using namespace std;
#include<bits/stdc++.h>
int arr[10000000];
int tree[1000000];
int n;

// build tree
void build(int val,int index)
{

while(index<=n)
{

tree[index]+=val;
index+=index & (-index);

}
}

// increase ith index value by val ..
void update(int val,int index)
{

int diff=val-arr[index];
arr[index]=val;
while(index<=n)
{

tree[index]+=diff;
index+=index & (-index);

}
}

// sum from index 1 to index
int query(int index)
{

int sum=0;
while(index!=0)
{
sum+=tree[index];
index-=index & (-index);
}
return sum;
}

int main()
{

cin>>n;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}

for(int i=1;i<=n;i++)
{
build(arr[i],i);
}

int q;
cin>>q;
while(q--)
{
int type ;
cin>>type;
if(type==1)
{
cout<<" enter value and index at which need to update !!!!"<<endl;
int val ,index;// index at which need to update if array is 1 based
cin>>val>>index;
update(val,index);
cout<<" tree status "<<endl;
for(int i=1;i<=n;i++) cout<<tree[i]<<" ";
cout<<endl;
}
else
{
int index;
cin>>index;// sum of fist index no of numbers ...
int ans=query(index);
cout<<ans<<endl;
}
}

}

BIT -- POINT INCREASE AND RANGE QUERY !!!!

https://www.youtube.com/results?search_query=binary+index++tree videotutorial
BIT -- POINT INCREASE AND RANGE QUERY !!!!

QUERY CAN BE OF TYPE SUM FROM INDEX 0 TO A ..

NOTE WE CAN CHANGE QUERY AS SUM FROM [a,b] IF WE CALL QUERY 2 TIMES
ie- query(b)-query(a-1).
-------------------------------------------CODE---------------------------------------------------------------------
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
int arr[10000000];
int tree[1000000];
int n;

// build tree
void build(int val,int index)
{

while(index<=n)
{

tree[index]+=val;
index+=index & (-index);

}
}

// increase ith index value by val ..
void update(int val,int index)
{

while(index<=n)
{

tree[index]+=val;
index+=index & (-index);

}
}

// sum from index 1 to index
int query(int index)
{

int sum=0;
while(index!=0)
{
sum+=tree[index];
index-=index & (-index);
}
return sum;
}

int main()
{

cin>>n;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}

for(int i=1;i<=n;i++)
{
build(arr[i],i);
}

int q;
cin>>q;
while(q--)
{
int type ;
cin>>type;
if(type==1)
{
int val ,index;// index at which need to update if array is 1 based
cin>>val>>index;
update(val,index);
cout<<" tree status "<<endl;
for(int i=1;i<=n;i++) cout<<tree[i]<<" ";
cout<<endl;
}
else
{
int index;
cin>>index;// sum of fist index no of numbers ...
int ans=query(index);
cout<<ans<<endl;
}
}

}

	# Add v to A[p]
	update(p, v):
	for (; p <= N; p += p&(-p))
	ft[p] += v

	# Add v to A[a...b]
	update(a, b, v):
	update(a, v)
	update(b + 1, -v)

	# Return A[b]
	query(b):
	sum = 0
	for(; b > 0; b -= b&(-b))
	sum += ft[b]
	return sum

Wednesday, 14 October 2015