1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;
typedef struct node{
    int key, val, num, lazy;
    long totalVal;
    struct node *left, *right, *father;
}Node;
Node* createNode(int key, int val) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->val = val;
    node->num = 1;
    node->totalVal = val;
    node->lazy = 0;
    node->left = NULL;
    node->right = NULL;
    node->father = NULL;
    return node;
}
void update(Node *x) {
    //here must initialize
    x->num = 1;
    x->totalVal = x->val;
    if(x->left) {
        x->num += x->left->num;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX