যে কাজে ব্যবহার করা যায় :
এটি দিয়ে কোন একটা array এর একটা ইনডেক্স থেকে অন্য ইনডেক্স এর মাঝের value গুলোর যোগফল বের করা যায় । if( i<j) sum=a[i] + ..... + a[j].
এটি দিয়ে কোন ইনডেক্স এর value change বা add করে পুনরায় একটা ইনডেক্স থেকে অন্য ইনডেক্স এর মাঝের value গুলোর যোগফল বের করা যায় ।
......................................................................................................................................................................................................................................................................................................................................শুরু :
#include<bits/stdc++.h>
using namespace std;
#define max 10000
int arr[max];
int tree[3*max];
int a,b;
void segtree(int node,int l,int r)
{
if(l==r)
{
tree[node]=arr[l];
return;
}
int Left=node*2;
int Right=node*2+1;
int mid=(l+r)/2;
segtree(Left,l,mid);
segtree(Right,mid+1,r);
tree[node]=tree[Left]+tree[Right];
}
long read(int node,int l,int r)
{
if(l>b||r<a)//over bundory
return 0;
if(l>=a&&r<=b)
return tree[node];
int Left=node*2;
int Right=node*2+1;
int mid=(l+r)/2;
int p1=read(Left,l,mid);
int p2=read(Right,mid+1,r);
return p1+p2;
}
void update(int node,int l,int r,int p,int val)//add value of a position
{
tree[node]+=val;
if(l==r)
return;
int Left=node*2;
int Right=node*2+1;
int mid=(l+r)/2;
if(p>=l&&p<=mid)
update(Left,l,mid,p,val);
else
update(Right,mid+1,r,p,val);
}
void update1(int node,int l,int r,int p,int newval) // new value of a position
{
if (p > r || p < l) return;
if (l >= p && r <= p) {
tree[node]=newval;
return;
}
int Left=node*2;
int Right=node*2+1;
int mid=(l+r)/2;
update1(Left,l,mid,p,newval);
update1(Right,mid+1,r,p,newval);
tree[node]=tree[Left]+tree[Right];
}
int main()
{
int n,i,value,position;
cin>>n;
for(i=1;i<=n;i++)
cin>>arr[i];
segtree(1,1,n);
cin>>a>>b;//sum of range a to b
cout<<read(1,1,n)<<endl;
cin>>position>>value; // position a value add .
update(1,1,n,position,value);
cin>>a>>b;//sum of range a to b
cout<<read(1,1,n)<<endl;
cin>>position>>value; // position a value change .
update1(1,1,n,position,value);
cin>>a>>b;//sum of range a to b
cout<<read(1,1,n)<<endl;
return 0;
}
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন