RMQ

#a693

1. Prefix Sum

#include <stdio.h>

int main(){
  int n,m,l,r;
  while(EOF!=scanf("%d %d",&n,&m)){
    int arr[100005]={0};
    int prefix[100005]={0};  
    for(int i=1;i<=n;i++){
      scanf("%d",&arr[i]);
      prefix[i]=prefix[i-1]+arr[i];
    }
    while(m--){
      scanf("%d %d",&l,&r);
      printf("%d\n",prefix[r]-prefix[l-1]);
    }
  }
  return 0;
}

2. Binary Index Tree

#include <stdio.h>
#include <string.h>


int tree[100005]={0};

void update(int val,int node,int maxN){
  while(node<=maxN){
    tree[node]+=val;
    node+=(node&-node);
  }
}

int query(int node){
  int sum=0;
  while(node>0){
    sum+=tree[node];
    node-=(node&-node);
  }
  return sum;
}

int main(){
  int n,m,l,r;
  while(EOF!=scanf("%d %d",&n,&m)){
    memset(tree,0,sizeof(tree));
    int x;
    for(int i=1;i<=n;i++){
      scanf("%d",&x);
      update(x,i,n);
    }
    while(m--){
      scanf("%d %d",&l,&r);
      printf("%d\n",query(r)-query(l-1));
    }
  }
  return 0;
}

3. Segment Tree

#include <stdio.h>

int arr[100000]={0};
int tree[400000]={0};

void built(int node,int l,int r){
  if(l==r){
    tree[node]=arr[l];
    return;
  }
  int mid=(l+r)/2;
  built(node*2+1,l,mid);
  built(node*2+2,mid+1,r);
  tree[node]=tree[node*2+1]+tree[node*2+2];
}

int query(int node,int l,int r,int i,int j){
  if(r<i||l>j) return 0;
  if((l==i&&r==j)||l==r) return tree[node];
  int mid=(l+r)/2;
  int left=query(node*2+1,l,mid,i,j);
  int right=query(node*2+2,mid+1,r,i,j);
  return left+right;
}

int main(){
  int n,m,l,r;
  while(EOF!=scanf("%d %d",&n,&m)){
    for(int i=0;i<n;i++){
      scanf("%d",&arr[i]);
    }
    built(0,0,n-1);
    while(m--){
      scanf("%d %d",&l,&r);
      printf("%d\n",query(0,0,n-1,l-1,r-1));
    }
  }
  return 0;
}