/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package SegmentTree;
import java.util.Scanner;
/**
*
* @author MyPC
*/
public class SegmentTree {
static int[] ST;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int sz = sc.nextInt();
int[] a = new int[sz];
ST = new int[4 * sz];
for(int i = 0; i < a.length; i++){
a = sc.nextInt();
}
System.out.println("finish get data");
int m = sc.nextInt();
System.out.println(ST[0]);
for (int i = 0 ; i< m ; i++ ) {
int n = sc.nextInt();
if (n == 1) {
int l = sc.nextInt();
int r = sc.nextInt();
System.out.println(getQuery(0, 0, a.length - 1, l-1, r-1, a));
}
else {
int id = sc.nextInt();
int value = sc.nextInt();
update(value, id, 0, 0, a.length - 1, a);
}
}
}
public static int construct(int saIdx, int left, int right ,int[] a) {
/*
Neu doan co do dai 1 thi chung ta biet no se la 1 nut ben trai
va no se chua 1 phan tu cau mang da cho
*/
if (left == right) {
return ST[saIdx] = a
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package SegmentTree;
import java.util.Scanner;
/**
*
* @author MyPC
*/
public class SegmentTree {
static int[] ST;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int sz = sc.nextInt();
int[] a = new int[sz];
ST = new int[4 * sz];
for(int i = 0; i < a.length; i++){
a = sc.nextInt();
}
System.out.println("finish get data");
int m = sc.nextInt();
System.out.println(ST[0]);
for (int i = 0 ; i< m ; i++ ) {
int n = sc.nextInt();
if (n == 1) {
int l = sc.nextInt();
int r = sc.nextInt();
System.out.println(getQuery(0, 0, a.length - 1, l-1, r-1, a));
}
else {
int id = sc.nextInt();
int value = sc.nextInt();
update(value, id, 0, 0, a.length - 1, a);
}
}
}
public static int construct(int saIdx, int left, int right ,int[] a) {
/*
Neu doan co do dai 1 thi chung ta biet no se la 1 nut ben trai
va no se chua 1 phan tu cau mang da cho
*/
if (left == right) {
return ST[saIdx] = a
;
}
/*
Phan doan nut cha chia lam 2 nua.
Neu phan doan cho cha la [ left,right],
thi phan doan nut con trai la : [left,mid],
phan doan nut con phai la : [mid+1,right].
*/
int mid = (left + right) / 2;
int leftChild = construct(2 * saIdx + 1, left, mid, a);
int rightChild = construct(2 * saIdx + 2, mid + 1, right, a);
ST[saIdx] = leftChild + rightChild;
return ST[saIdx];
}
// saIdx : con tro cho mang ST
// left : gioi han trai cay ST
// right : gioi han phai cay ST
// l : gioi han trai cua doan truy van da cho
// r : gioi han phai cua doan truy van da cho
public static int getQuery(int saIdx, int left, int right, int l, int r, int[] a) {
if (left > r || right == l && right <= r) {
return ST[saIdx];
}
else {
int mid = (left + right) / 2;
int leftResult;
int rightResult;
leftResult = (getQuery(2*saIdx+1, left, mid, l , r, a));
rightResult = (getQuery(2*saIdx+2 , mid + 1, right, l, r, a));
return leftResult + rightResult;
}
}
public static void update(int value, int id, int saIdx, int left, int right, int[] a) {
// neu chi so cho nam ngoai phan doan thi ko can cap nhat
if (id < left || id > right ) {
return ;
}
/*
Neu tim thay index duoc cap nhat -> cap nhat mang da cho
cung nhu mang doan truy van da cho
*/
if (id == left && id == right) {
a
}
/*
Phan doan nut cha chia lam 2 nua.
Neu phan doan cho cha la [ left,right],
thi phan doan nut con trai la : [left,mid],
phan doan nut con phai la : [mid+1,right].
*/
int mid = (left + right) / 2;
int leftChild = construct(2 * saIdx + 1, left, mid, a);
int rightChild = construct(2 * saIdx + 2, mid + 1, right, a);
ST[saIdx] = leftChild + rightChild;
return ST[saIdx];
}
// saIdx : con tro cho mang ST
// left : gioi han trai cay ST
// right : gioi han phai cay ST
// l : gioi han trai cua doan truy van da cho
// r : gioi han phai cua doan truy van da cho
public static int getQuery(int saIdx, int left, int right, int l, int r, int[] a) {
if (left > r || right == l && right <= r) {
return ST[saIdx];
}
else {
int mid = (left + right) / 2;
int leftResult;
int rightResult;
leftResult = (getQuery(2*saIdx+1, left, mid, l , r, a));
rightResult = (getQuery(2*saIdx+2 , mid + 1, right, l, r, a));
return leftResult + rightResult;
}
}
public static void update(int value, int id, int saIdx, int left, int right, int[] a) {
// neu chi so cho nam ngoai phan doan thi ko can cap nhat
if (id < left || id > right ) {
return ;
}
/*
Neu tim thay index duoc cap nhat -> cap nhat mang da cho
cung nhu mang doan truy van da cho
*/
if (id == left && id == right) {
a
= value;
ST[saIdx] = value;
}
/*
cap nhat tat ca cac nut co chua index da cho trong doan cua no
*/
else {
int mid = (left + right) / 2;
update(value, id, 2*saIdx + 1, left, mid, a);
update(value, id, 2*saIdx + 2, mid + 1, right, a);
ST[saIdx] = ST[2 * saIdx + 1] + ST[2 * saIdx + 2];
}
}
}
ST[saIdx] = value;
}
/*
cap nhat tat ca cac nut co chua index da cho trong doan cua no
*/
else {
int mid = (left + right) / 2;
update(value, id, 2*saIdx + 1, left, mid, a);
update(value, id, 2*saIdx + 2, mid + 1, right, a);
ST[saIdx] = ST[2 * saIdx + 1] + ST[2 * saIdx + 2];
}
}
}