---
title: CHV training [1]
---

## Bedao Regular Contest 11 - EVENSUM

___
> ###### Tags: Segment Tree.
> https://oj.vnoi.info/problem/bedao_r11_evensum
___
### **Nhận xét** :
+ Giả sử gọi $s_i = a_1 + a_2.. + a_i$.
+ Ta có thể nhận ra rằng một đoạn $[l, r]$ có tổng là chẵn khi $s_r$ và $s_{l-1}$ cùng chẵn hay cùng lẻ. Từ đó suy ra số đoạn con của đoạn $[l, r]$ có tổng chẵn sẽ là :
+ Gọi lần lượt $\;x, \;y\;$ là số lượng $s_i$ có tổng là chẵn và lẻ trong đoạn $[l - 1, \; r]$ .
+ Số đoạn con = $x \;* \;(x - 1) \;/ \;2 \;+\; y\; * \;(y - 1)\; / \;2$.
+ Với mỗi truy vấn $1 \:\: k \:\: b$:
+ Nếu $\;a_k\;$ và $\;b\;$ cùng chẵn hoặc cũng lẻ thì không thay đổi bất cứ điều gì !
+ Ngược lại tất cả những $s_i (k <= i <= n)$ sẽ thay đổi tính chất, từ chẵn thành lẻ và ngược lại.

$=>$ Từ những nhận xét trên ta có thể dùng **Segment Tree** để quản lí tính chất chẵn lẻ của các $s_i$.

> Bạn có thể tham khảo bài : https://oj.vnoi.info/problem/lites/. Để giải được bài này !.