HackerEarth Binary Modulo P2SME problem solution

1. 0 L R – Tell the remainder of the Number(in Decimal) represented by the Binary String between indexes L and R when divided by 5.
2. 1 X V – Replace character at position X with V.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <math.h>

#define ll long long int
#define maxN 10000
#define maxVal 100000000
#define minVal -100000000
#define mod 1000000007LL

#define gcd(a,b) __gcd(a,b)

using namespace std;

struct data
{
    int v,c;
};

int p[maxN+5];

int n;
char a[maxN+5];
data tree[3*maxN+5];

void pre()
{
    int i;
    p[0]=1;
    for(i=1;i<=maxN;i++)
        p[i]=(2*p[i-1])%5;
}

data makeNode(int v)
{
    data x;
    x.v=v;
    x.c=1;
    return x;
}

data combine(data l,data r)
{
    data x;
    x.v=((l.v*p[r.c])%5+r.v)%5;
    x.c=l.c+r.c;
    return x;
}

void build(int node,int start,int end)
{
    if(start==end)
    {
        tree[node]=makeNode(a[start]-'0');
        return;
    }
    int mid=start+(end-start)/2;
    build(2*node+1,start,mid);
    build(2*node+2,mid+1,end);
    tree[node]=combine(tree[2*node+1],tree[2*node+2]);
}

data query(int node,int start,int end,int l,int r)
{
    if(start>=l&&end<=r)
        return tree[node];
    int mid=start+(end-start)/2;
    if(l>mid)
        return query(2*node+2,mid+1,end,l,r);
    if(r<=mid)
        return query(2*node+1,start,mid,l,r);
    return combine(query(2*node+1,start,mid,l,r),query(2*node+2,mid+1,end,l,r));
}

void update(int node,int start,int end,int i,int v)
{
    if(start==end)
    {
        tree[node]=makeNode(v);
        return;
    }
    int mid=start+(end-start)/2;
    if(i<=mid)
        update(2*node+1,start,mid,i,v);
    else
        update(2*node+2,mid+1,end,i,v);
    tree[node]=combine(tree[2*node+1],tree[2*node+2]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t,q,l,r,c;
    pre();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%d",a,&q);
        n=strlen(a);
        build(0,0,n-1);
        while(q--)
        {
            scanf("%d%d%d",&c,&l,&r);
            if(c==0)
                printf("%dn",query(0,0,n-1,l,r).v);
            else
                update(0,0,n-1,l,r);
        }
    }
    return 0;
}