Editorial - ECJN208

PROBLEM LINK:

Practice

Encoding June 2020 Contest

Author: arnie8991

Tester: sandeep1103

Editorialist: arnie8991

DIFFICULTY:

MEDIUM

PREREQUISITES:

Segment Trees

Problem

The children in the school are to have their final results announced today! There are in total 1-N roll numbers of students. The children have received their scores but are unhappy with the marks they received. So they flock around teacher A in large groups to increase their marks. While at the same time, another teacher, Teacher B asks the students to say their marks. However, teacher B has a weird habit. She likes to note down the sum of the marks of the students in a range of roll numbers and notes down the average roll number in the range.

Your task is to keep track of the marks of the students and also give teacher B the current average marks of a range of roll numbers.

EXPLANATION:

This is a problem in which if we take the naive approach of updating and querying a range, it will give us TLE. So we need to execute both these kinds of actions in log N time and hence we use the Segment Tree data structure. Segment Tree is able to perform each operation in O(log N) time. It takes O(N) to build the segment tree and thus we can build the tree and execute all the tasks in O(N) + O(QLogN) time, where Q is the number of queries.

SOLUTIONS:

Setter's Solution

    // All imports here

    import java.io.BufferedReader;

    import java.io.IOException;

    import java.io.InputStream;

    import java.io.InputStreamReader;

    import java.io.OutputStream;

    import java.io.PrintWriter;

    import java.util.Arrays;

    import java.util.List;

    import java.util.Map;

    import java.util.Set;

    import java.util.StringTokenizer;

    import java.util.stream.Collectors;

    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    public class Main {

        public static void main(String[] args) {

            InputStream inputStream = System.in;

            OutputStream outputStream = System.out;

            InputReader in = new InputReader(inputStream);

            PrintWriter out = new PrintWriter(outputStream);

            Task solver = new Task();

            int test = 1;

            while(test-->0){

                solver.solve(1, in, out);

            }

            out.close();

        }

    }

    class InputReader {

        public BufferedReader reader;

        public StringTokenizer tokenizer;

    

        public InputReader(InputStream stream) {

            reader = new BufferedReader(new InputStreamReader(stream));

            tokenizer = null;

        }

    

        public String next() {

            while (tokenizer == null || !tokenizer.hasMoreTokens()) {

                try {

                    tokenizer = new StringTokenizer(reader.readLine());

                } catch (IOException e) {

                    throw new RuntimeException(e);

                }

            }

            return tokenizer.nextToken();

        }

    

        public int nextInt() {

            return Integer.parseInt(next());

        }

        public long nextLong() {

            return Long.parseLong(next());

        }

        public Double nextDouble() {

            return Double.parseDouble(next());

        }

        public float nextFloat() {

            return Float.parseFloat(next());

        }

    

    }

    class Task {

        final long MOD = (int)Math.pow(10,9)+7;

        public void solve(int testNumber, InputReader sc, PrintWriter out) {

            

            // write your code here

            int n = sc.nextInt();

            int arr[] = new int[n];

            for(int i = 0; i < n; ++i){

                arr[i] = sc.nextInt();

            }

            SegmentTree st = new SegmentTree(n, arr);

            int q = sc.nextInt();

            for(int i = 0; i < q; i++){

                int a = sc.nextInt();

                int b = sc.nextInt();

                int c = sc.nextInt();

                if (a == 0){

                    //update operation

                    st.updateValue(0, n-1, b-1, c, 0);

                } 

                else {

                    //sum operation

                    long sum = st.getSum(0, n-1, b-1, c-1, 0);

                    long averagesum = (int)Math.ceil(sum / (c - b + 1.0));

                    out.println(averagesum);

                }

            }

        }

        class SegmentTree{

            int st[];

            SegmentTree(int n, int[] arr){

                st = new int[5*n];

                createST(arr, 0, n-1, 0);

            }

            public int createST(int arr[], int l, int r, int index){

                if (l == r){

                    st[index] = arr[l];

                    return st[index];

                }

                int mid = getMid(l, r);

                return st[index] = createST(arr, l, mid, index*2+1) + createST(arr, mid+1, r, index*2+2);

            }

            public int getMid(int l, int r) {

                return l + (r - l)/2;

            }

            public long getSum(int ss, int se, int qs, int qe, int si){

                

                if (qs <= ss && qe >= se) 

                    return st[si]; 

    

                if (se < qs || ss > qe) 

                    return 0; 

        

                int mid = getMid(ss, se); 

                return getSum(ss, mid, qs, qe, 2 * si + 1) + getSum(mid + 1, se, qs, qe, 2 * si + 2); 

            }

            void updateValue(int ss, int se, int i, int diff, int si) { 

                if (i < ss || i > se) 

                    return; 

                st[si] = st[si] + diff; 

                if (se != ss) { 

                    int mid = getMid(ss, se); 

                    updateValue(ss, mid, i, diff, 2 * si + 1); 

                    updateValue(mid + 1, se, i, diff, 2 * si + 2); 

                } 

            } 

        }

    }

1 Like

Segment tree is an overkill for this problem even standard Fenwick tree will do the job :

FENWICK_TREE_SOLUTION
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define For(i,n) for(int i=0;i<n;i++)
const long mxN =1e5+2 ;
int n,q ,m[mxN];
struct ft{
  ll a[mxN]={};
  void upd(int i,ll x){
    for(;i<=mxN;i+=i&-i)
      a[i]+=x ;
  }
  void upd1(int l,int r,ll x ){
    upd(l,x);upd(r+1,-x) ;
  }
  ll qry(int i){
    ll r=0 ;
    for(;i;i-=i&-i)
      r+=a[i] ;
    return r ;
  }
}f;
int main() {
  cin >> n  ;
  For(i,n){
    cin >> m[i] ;
    f.upd(i+1,m[i]) ;
  }
  cin >> q ;
  while(q--){
    int a,b,c;cin>> a >> b >> c ;
    if(a){
      int s = f.qry(c)-f.qry(b-1) ;
      int x= c-b+1 ;
      cout << (s+x-1)/x << endl ;
    }else{
      f.upd(b,c) ;
    }
  }
	return 0;
}

Well Fenwick is just an easier alternative to Seg-trees. And yeah it works just fine. Either of those would do.