Count Number of Substrings have count of 1s more than 0s | Hard | Segment Tree

https://practice.geeksforgeeks.org/problems/f72994353d123b925ff20f0694b662191df03ea2/1?page=1&difficulty[]=1&difficulty[]=2&status[]=unsolved&category[]=Dynamic%20Programming&category[]=Binary%20Search&category[]=Trie&category[]=union-find&sortBy=submissions

Given a binary string S consists only of 0s and 1s. The task is to calculate the number of substrings that have more 1s than 0s.

Example 1:
Input:
S = "011"
Output: 4
Explanation: There are 4 substring which
has more 1s than 0s. i.e "011","1","11" and "1"

Example 2:
Input:
S = "0000"
Output: 0
Explanation: There is no substring
which has more 1s than 0s

Constraints:
1 < |S| < 10^5
|S| denotes the length of the string S
---------------------------------------------------------------------------------------------------------------------------------------


class Solution{
private:
    vector<int> tree;
public:
  void update(int start, int end, int parent, long long index){
      if(start>end){
          return;
      }
      if(start==end){
          tree[parent]++;
          return;
      }
      int mid=(start+end)/2;
      if(index>mid){
          update(mid+1,end,2*parent+2,index);
      }
      else{
          update(start,mid,2*parent+1,index);
      }
      tree[parent]=tree[2*parent+1]+tree[2*parent+2];
  }

  int query(int start, int end, int parent, int qstart, int qend){
      if(qstart>end || qend<start){
          return 0;
      }
      if(qstart<=start && qend>=end){
          return tree[parent];
      }
      int mid=(start+end)/2;
      int L=query(start,mid,2*parent+1,qstart,qend);
      int R=query(mid+1,end,2*parent+2,qstart,qend);
      return L+R;
  }

  long long countSubstring(string S){
      int n=S.size();
      tree.resize(4*2*n+1,0);

      int shift=n;
      long long currSum=0;
      long long res=0;

      update(0,2*n,0,0+shift);
      for(int i=0;i<n;i++){
          currSum+=(S[i]=='1' ? 1 : -1);

          /*    prefix[j]-prefix[i]>=1
             or,prefix[i]<=1-prefix[j]
          */
          int lessThan=(currSum+shift)-1;
          res+=query(0,2*n,0,0,lessThan);

          update(0,2*n,0,currSum+shift);
      }
      return res;
  }
};