In this HackerEarth Super Power of 2s problem, Maggu loves to create problems involving queries. This time ,he has created one for you.
Given an array containing n elements and maggu asked you two types of queries.

type 0 : l r
type 1 : l r

HackerEarth Super Power Of 2s problem solution


HackerEarth Super Power Of 2s problem solution.

#include<bits/stdc++.h>
using namespace std;
#define scan(a) scanf("%d",&a)
#define scanll(a) scanf("%lld",&a)
#define print(a) printf("%d",a)
#define printll(a) printf("%lld\n",a)
#define FOR(i,a,n) for(int i=a;i<n;i++)
#define VI vector<int>
#define VLL vector<long long >
#define ll long long
#define MOD 1000000007
#define MAX 200001
VLL arr,PW;
// power calculation
void pre_process(int n){
 PW.resize(n+1);
 PW[0]=1;
 int i;
 FOR(i,1,n+1){
   PW[i]=(2*PW[i-1])%MOD;
 }
 FOR(i,1,n+1){
   PW[i]=(PW[i]+PW[i-1])%MOD;
 }
}
ll st[4*MAX]; // build auto
ll A[4*MAX];
bool F[4*MAX];

void adjust(int idx,int ss,int se){

     st[idx]=(st[idx]+((A[idx]%MOD)*((PW[se-ss])%MOD))%MOD)%MOD;
     int mid=(ss+se)>>1;
     if(ss!=se){
       A[2*idx+1]=(A[2*idx+1]+A[idx])%MOD;
       A[2*idx+2]=(A[2*idx+2]+((A[idx]%MOD)*(((PW[mid-ss+1]-PW[mid-ss])%MOD+MOD)%MOD))%MOD)%MOD;
       F[2*idx+1]=F[2*idx+2]=true;
     }
     F[idx]=0;
     A[idx]=0;
     return ;
}

void update(int idx,int ss,int se,int l,int r){

   if(F[idx])adjust(idx,ss,se);
   if(l>se||r<ss) return ;
   if(l<=ss&&se<=r){
     st[idx]=(st[idx]%MOD+((PW[se-l+1]-PW[ss-l])%MOD+MOD)%MOD)%MOD;
     if(ss!=se){
       int mid=(ss+se)>>1;
       A[2*idx+1]=(A[2*idx+1]+((PW[ss-l+1]-PW[ss-l])%MOD+MOD)%MOD)%MOD;
       A[2*idx+2]=(A[2*idx+2]+((PW[mid-l+2]-PW[mid+1-l])%MOD+MOD)%MOD)%MOD;
       F[2*idx+1]=F[2*idx+2]=true;
     }
     return ;
   }
   int  mid=(ss+se)>>1;
   update(2*idx+1,ss,mid,l,r);
   update(2*idx+2,mid+1,se,l,r);
   st[idx]=(st[2*idx+1]+st[2*idx+2])%MOD;
}

ll query(int idx,int ss,int se,int l,int r){
  if(F[idx]) adjust(idx,ss,se);
  if(l>se||r<ss) return 0;
  if(l<=ss&&se<=r) return st[idx]%MOD;
  int mid=(ss+se)>>1;
  ll L=query(2*idx+1,ss,mid,l,r);
  ll R=query(2*idx+2,mid+1,se,l,r);
  return (L+R)%MOD;
}

int main(){
int n;
scan(n);
pre_process(n);
arr.resize(n+1);
int i;
FOR(i,1,n+1){
 ll x;
 scanll(x);
 arr[i]=(x+arr[i-1])%MOD;
}
int q;
scan(q);
while(q--){
 int c,l,r;
 scan(c);
 scan(l);l--;
 scan(r);r--;
 if(!c){
   update(0,0,n-1,l,r);
 }else{
   ll ans1=query(0,0,n-1,l,r)%MOD;
   ll ans2=((arr[r+1]-arr[l])%MOD+MOD)%MOD;
   ans1=(ans1+ans2)%MOD;
   printll(ans1);
 }
}
return 0;
}

Second solution

#include <bits/stdc++.h>

#define M 1000000007

int A[200001];
int tree[700005];
int lazy[700005];
bool flag[700005];
int p2[200001];
int dp[200001];

using namespace std;

inline void fi(int *a)
{
 register char c=0;
 while (c<33) c=getchar_unlocked();
 *a=0;
 int tmp = 0;
 while (c>33)
 {
     if ( c == 45 ) tmp = 1;
     else *a=*a*10+c-'0';
     c=getchar_unlocked();
 }
 if ( tmp == 1 ) *a = 0-(*a);
}

void pre()
{
    p2[0] = 1;
    for ( int i = 1; i <= 200000; i++ ) {
        p2[i] = p2[i-1]*2;
        if ( p2[i] >= M ) p2[i] -= M;
    }
    return;
}

void build(int node, int left, int right)
{
    if ( left > right ) return;
    if ( left == right ) {
        tree[node] = A[left];
        return;
    }
    int mid = (left+right)>>1;
    build(node<<1, left, mid);
    build((node<<1)|1, mid+1, right);
    tree[node] = (tree[node<<1] + tree[(node<<1)|1]);
    if ( tree[node] >= M ) tree[node] -= M;
}

void pushdown(int node, int left, int right)
{
    int mid = (left+right)>>1;
    if ( flag[node] ) {
        int val = (p2[right-left+1]-1);
        if ( val < 0 ) val += M;
        val = ((long long)val*(long long)lazy[node])%M;
        tree[node] = (tree[node]+val);
        if ( tree[node] >= M ) tree[node] -= M;
        if ( left != right ) {
            lazy[node<<1] = (lazy[node<<1]+lazy[node]);
            lazy[(node<<1)|1] = (lazy[(node<<1)|1]+((long long)p2[mid+1-left]*(long long)lazy[node])%M);
            if ( lazy[node<<1] >= M ) lazy[node<<1] -= M;
            if ( lazy[(node<<1)|1] >= M ) lazy[(node<<1)|1] -= M;
            flag[node<<1] = flag[(node<<1)|1] = true;
        }
        lazy[node] = 0;
        flag[node] = false;
    }
    return;
}

void update(int node, int left, int right, int i, int j)
{
    pushdown(node, left, right);
    if ( left > right|| left > j || right < i ) return;
    int mid = (left+right)>>1;
    if ( left >= i && right <= j ) {
        int val1 = p2[left-i+1];
        int val2 = (p2[right-left+1]-1);
        if ( val2 < 0 ) val2 += M;
        val1 = ((long long)val1*(long long)val2)%M;
        tree[node] = (tree[node] + val1);
        if ( tree[node] >= M ) tree[node] -= M;
        if ( left != right ) {
            lazy[node<<1] = (lazy[node<<1]+p2[left-i+1]);
            lazy[(node<<1)|1] = (lazy[(node<<1)|1]+p2[mid+1-i+1]);
            if ( lazy[node<<1] >= M ) lazy[node<<1] -= M;
            if ( lazy[(node<<1)|1] >= M ) lazy[(node<<1)|1] -= M;
            flag[node<<1] = flag[(node<<1)|1] = true;
        }
        return;
    }
    update(node<<1, left, mid, i, j);
    update((node<<1)|1, mid+1, right, i, j);
    tree[node] = (tree[node<<1] + tree[(node<<1)|1]);
    if ( tree[node] >= M ) tree[node] -= M;
}

int query(int node, int left, int right, int i, int j)
{
    pushdown(node, left, right);
    if ( left > right || left > j || right < i ) return 0;
    if ( left >= i && right <= j ) return tree[node];
    int mid = (left+right)>>1;
    int p = query(node<<1, left, mid, i, j) + query((node<<1)|1, mid+1, right, i, j);
    if ( p >= M ) p -= M;
    return p;
}

int main()
{
    pre();
    int n,q,type,x,y;
    fi(&n);
    bool ff = false;
    for ( int i = 0; i < n; i++ ) {
        fi(&A[i]);
        if ( i != 0 ) dp[i] = dp[i-1] + A[i];
        else dp[i] = A[i];
        if ( dp[i] >= M ) dp[i] -= M;
    }
    build(1,0,n-1);
    fi(&q);
    while ( q-- ) {
        fi(&type); fi(&x); fi(&y);
        x--; y--;
        if ( type == 0 ) {
             update(1,0,n-1,x,y);
             ff = true;
        }
        else {
             if ( !ff ) {
                  int ans;
                  if ( x == 0 ) ans = dp[y];
                  else {
                       ans = dp[y]-dp[x-1];
                       if ( ans < 0 ) ans += M;
                  }
                  printf("%d\n", ans);
             }
             else printf("%d\n", query(1,0,n-1,x,y));
        }            
    }
    return 0;
}